Loading…

hardArraysLC #42Frequently asked

Trapping Rain Water

Q: How do you solve Trapping Rain Water using the Prefix-Max & Suffix-Max Arrays approach?

When to use it: Say it first — it makes the water formula explicit and is the clearest correct baseline before optimizing space. (Mention the naive O(n²) per-column scan, then improve to this.) First derive the local rule: a bar at index `i` holds water up to the lower of the tallest wall on its left and the tallest wall on its right, minus its own height. The naive way to get those two walls is to scan left and right for every bar — correct, but that's O(n²) because the scans overlap massively. **Eliminate the repeated scans with precomputation.** Build two arrays in single passes: `maxLeft[i]` = the maximum of `height[0..i]`, and `maxRight[i]` = the maximum of `height[i..n-1]`. Each is a simple running max — left-to-right for the prefix, right-to-left for the suffix. **Then the answer is one more pass.** For each `i`, the trapped water is `min(maxLeft[i], maxRight[i]) − height[i]`. This is never negative: `maxLeft[i] ≥ height[i]` and `maxRight[i] ≥ height[i]` by construction, so their min is at least `height[i]`. Sum the contributions. **Why this is the right baseline to present.** It converts the vague picture of pooling water into a precise, obviously-correct formula and runs in optimal O(n) time. Its only weakness is the two O(n) arrays — which is exactly the thing the two-pointer method removes, so it's the perfect springboard. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Trapping Rain Water using the Two Pointers — Running Maxes (Optimal) approach?

When to use it: The answer they want for a hard problem. Phrase it as 'I don't need the whole prefix/suffix arrays — two running maxes and two pointers suffice'. Keep two pointers `l` and `r` at the ends and two running maxes `leftMax`, `rightMax`. At each step compare `height[l]` and `height[r]` and process the *smaller* side. **Why processing the smaller side is correct — the key argument.** Suppose `height[l] height[l]`, so the true right max is at least `height[r] > height[l] ≥ … `. The binding constraint for bar `l` is therefore the left side: `min(leftMaxTrue, rightMaxTrue) = leftMax` here, because `leftMax ≤ height[r] ≤ rightMaxTrue`. In other words, whenever the left bar is the shorter of the two ends, the left running max alone determines bar `l`'s water — we can commit it and move on. The symmetric statement holds for the right side. **Why update the max before adding water.** We set `leftMax = max(leftMax, height[l])` *first*. If the current bar is the tallest seen so far on the left, `leftMax` becomes `height[l]` and it contributes `leftMax − height[l] = 0` — correctly trapping nothing rather than a negative amount. **Why this drops the O(n) arrays.** The prefix/suffix solution stored every max so it could look them up later. But by always advancing the side whose end bar is shorter, we only ever need the running max behind the pointer we're moving — the other side's max is guaranteed to be at least as large. So two scalars replace two arrays. **Why O(n) time and O(1) space.** Each element is visited once as a pointer passes it, and the only state is four integers (two pointers, two maxes) plus the accumulator. Time complexity: O(n). Space complexity: O(1).

LCPractice

Two Pointers · 4 of 30 · 12 min

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

In plain English

Each bar can hold a column of water whose top is the lower of the tallest bar to its left and the tallest bar to its right; subtract the bar's own height. Sum these columns. The ends never trap water, and any bar taller than both surrounding maxes traps nothing.

Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Note: The dips between taller bars hold 6 units total (classic LeetCode picture).

Example 2

Input: height = [4,2,0,3,2,5]
Output: 9
Note: Between the 4 on the left and 5 on the right, the valley traps 9 units.

Example 3

Input: height = [3, 2, 1]
Output: 0
Note: Strictly descending — no right wall ever rises again, so nothing is trapped.

Constraints

n == height.length
1 ≤ n ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵

Clarifying questions4First question: How much water sits above a single bar?Explore questions

Q1.How much water sits above a single bar?
min(tallest to the left, tallest to the right) − the bar's own height, clamped at zero.
Q2.Do the leftmost and rightmost bars trap water?
No — there's no taller wall on the outside to contain it, so their contribution is zero.
Q3.Can heights be zero or flat?
Yes. Flat or descending terrain traps nothing; the formula naturally yields zero.
Q4.Is O(1) extra space expected?
The prefix/suffix-array solution is O(n) space and clear; the two-pointer solution achieves O(1) and is the target for a hard problem.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Water above bar i = min(maxLeft[i], maxRight[i]) − height[i], summed over all i. The clear baseline precomputes prefix-max and suffix-max arrays in O(n) time and O(n) space. The interview-grade answer is two pointers with running leftMax/rightMax: process whichever side has the smaller max, because that side's water is fully determined. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the local water formula min(maxLeft, maxRight) − height, then progress from O(n)-space prefix/suffix arrays to an O(1)-space two-pointer pass with a correct argument for which side to advance.

Where candidates slip

Reasoning about water column-by-column with nested scans (O(n²)), or in the two-pointer version advancing the wrong side / updating the max after adding water.

How to stand out

Derive the per-bar formula, present the prefix/suffix-array solution, then explain why advancing the shorter side lets you drop those arrays. Articulate why the smaller side's max alone bounds its water.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Prefix-Max & Suffix-Max Arrays	`O(n)`	`O(n)`	Say it first — it makes the water formula explicit and is the clearest correct baseline before optimizing space. (Mention the naive O(n²) per-column scan, then improve to this.)	Read
2	Two Pointers — Running Maxes (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want for a hard problem. Phrase it as 'I don't need the whole prefix/suffix arrays — two running maxes and two pointers suffice'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewTotal trapped waterIs O(1) extra space required?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Prefix-Max & Suffix-Max Arrays

TimeO(n)SpaceO(n)

Say it first — it makes the water formula explicit and is the clearest correct baseline before optimizing space. (Mention the naive O(n²) per-column scan, then improve to this.)

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start naive: for each bar, scan left for the tallest bar and right for the tallest bar; water above it is min(those two) − height. That's correct but O(n²).

2Hint 2Explore hint

The two scans recompute the same maxes repeatedly. Precompute them: maxLeft[i] = tallest bar in [0..i], maxRight[i] = tallest bar in [i..n-1].

3Hint 3Explore hint

Then water = sum over i of (min(maxLeft[i], maxRight[i]) − height[i]). Two passes to build the arrays, one pass to sum.

A · Core idea

First derive the local rule: a bar at index i holds water up to the lower of the tallest wall on its left and the tallest wall on its right, minus its own height. The naive way to get those two walls is to scan left and right for every bar — correct, but that's O(n²) because the scans overlap massively.

Eliminate the repeated scans with precomputation. Build two arrays in single passes: maxLeft[i] = the maximum of height[0..i], and maxRight[i] = the maximum of height[i..n-1]. Each is a simple running max — left-to-right for the prefix, right-to-left for the suffix.

Then the answer is one more pass. For each i, the trapped water is min(maxLeft[i], maxRight[i]) − height[i]. This is never negative: maxLeft[i] ≥ height[i] and maxRight[i] ≥ height[i] by construction, so their min is at least height[i]. Sum the contributions.

Why this is the right baseline to present. It converts the vague picture of pooling water into a precise, obviously-correct formula and runs in optimal O(n) time. Its only weakness is the two O(n) arrays — which is exactly the thing the two-pointer method removes, so it's the perfect springboard.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

height = [4, 2, 0, 3, 2, 5]

maxLeft

running max L→R

State[4,4,4,4,4,5]

Final result9

C · Code with teaching comments

Reference implementation previewpublic int trap(int[] height) { int n = height.length; if (n == 0) return 0; int[] maxLeft = new int[n]; int[] maxRight = new int[n];Explore the full code

solution.javaJava

Prefix-Max & Suffix-Max Arrays — reference

3 teaching notes

1
public int trap(int[] height) {
2
    int n = height.length;
3
    if (n == 0) return 0;
4
    int[] maxLeft = new int[n];
5
    int[] maxRight = new int[n];
6
    maxLeft[0] = height[0];
7
    for (int i = 1; i < n; i++) {
8
        // Running max from the left — tallest wall at or before i.
9
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
10
    }
11
    maxRight[n - 1] = height[n - 1];
12
    for (int i = n - 2; i >= 0; i--) {
13
        // Running max from the right — tallest wall at or after i.
14
        maxRight[i] = Math.max(maxRight[i + 1], height[i]);
15
    }
16
    int water = 0;
17
    for (int i = 0; i < n; i++) {
18
        // Water above bar i; non-negative because both maxes ≥ height[i].
19
        water += Math.min(maxLeft[i], maxRight[i]) - height[i];
20
    }
21
    return water;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The naive O(n²) version recomputes 'tallest to the left/right' for every bar. Caching those as prefix-max and suffix-max arrays is a textbook DP move: identify a repeated sub-result and precompute it. Once you see the answer depends only on two running maxes, you can wonder whether you even need to store the whole arrays — and you don't.

ComplexityO(n) time, O(n) space — Three linear passes (build prefix-max, build suffix-max, sum) = O(n) time. Two auxiliary arrays of length n → O(n) space.

E · Edge cases and pitfalls3Computing the maxes with nested scans instead of running maxes — back to O(n²).Explore edge cases

Pitfalls

Computing the maxes with nested scans instead of running maxes — back to O(n²).
Initializing the suffix array left-to-right by mistake.
Forgetting that the result per bar is guaranteed non-negative only because the maxes include the bar itself.

03.2

Approach 2 of 2 · Optimal

Two Pointers — Running Maxes (Optimal)

TimeO(n)SpaceO(1)

The answer they want for a hard problem. Phrase it as 'I don't need the whole prefix/suffix arrays — two running maxes and two pointers suffice'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In the array solution, water at i needs only min(maxLeft[i], maxRight[i]). What if you tracked leftMax and rightMax on the fly with two pointers?

2Hint 2Explore hint

Put l at the start, r at the end. If height[l] < height[r], then the left side's water is limited by leftMax regardless of what's deeper on the right — because some bar on the right (height[r]) is already at least as tall.

3Hint 3Explore hint

So when height[l] < height[r], update leftMax and add leftMax − height[l], then l++. Otherwise do the symmetric thing on the right with r--.

A · Core idea

Keep two pointers l and r at the ends and two running maxes leftMax, rightMax. At each step compare height[l] and height[r] and process the smaller side.

Why processing the smaller side is correct — the key argument. Suppose height[l] < height[r]. Water above bar l equals min(leftMaxTrue, rightMaxTrue) − height[l], where the 'true' maxes are over the whole array. We don't know rightMaxTrue exactly, but we do know there's a bar at index r with height[r] > height[l], so the true right max is at least height[r] > height[l] ≥ … . The binding constraint for bar l is therefore the left side: min(leftMaxTrue, rightMaxTrue) = leftMax here, because leftMax ≤ height[r] ≤ rightMaxTrue. In other words, whenever the left bar is the shorter of the two ends, the left running max alone determines bar l's water — we can commit it and move on. The symmetric statement holds for the right side.

Why update the max before adding water. We set leftMax = max(leftMax, height[l]) first. If the current bar is the tallest seen so far on the left, leftMax becomes height[l] and it contributes leftMax − height[l] = 0 — correctly trapping nothing rather than a negative amount.

Why this drops the O(n) arrays. The prefix/suffix solution stored every max so it could look them up later. But by always advancing the side whose end bar is shorter, we only ever need the running max behind the pointer we're moving — the other side's max is guaranteed to be at least as large. So two scalars replace two arrays.

Why O(n) time and O(1) space. Each element is visited once as a pointer passes it, and the only state is four integers (two pointers, two maxes) plus the accumulator.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

height = [4, 2, 0, 3, 2, 5]

Array state

l=1, r=5

left 2 < right 5; leftMax 4; +2 water

[0]

l ↓

[1]

[2]

[3]

[4]

r ↓

[5]

Current pointerResolved stateNot processed

Final result9

C · Code with teaching comments

solution.javaJava

Two Pointers — Running Maxes (Optimal) — optimal

4 teaching notes

1
public int trap(int[] height) {
2
    int l = 0, r = height.length - 1;
3
    int leftMax = 0, rightMax = 0;
4
    int water = 0;
5
    while (l < r) {
6
        // Left end is shorter → the right side is guaranteed tall enough, so left's
7
        // water is decided by leftMax.
8
        if (height[l] < height[r]) {
9
            // Update the running max BEFORE adding water so the tallest-so-far bar
10
            // traps zero, not negative.
11
            leftMax = Math.max(leftMax, height[l]);
12
            // Commit bar l's trapped water and never revisit it.
13
            water += leftMax - height[l];
14
            l++;
15
        } else {
16
            rightMax = Math.max(rightMax, height[r]);
17
            water += rightMax - height[r];
18
            r--;
19
        }
20
    }
21
    return water;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The leap is realizing that for the shorter end, the far side is already known to be tall enough — so that bar's water is fully decided by the near running max. That 'the smaller side is fully resolved' observation is what lets two pointers replace the prefix/suffix arrays, turning an O(n)-space DP into an O(1)-space sweep.

ComplexityO(n) time, O(1) space — Each iteration advances one of the two pointers and they never separate, so the loop runs at most n times → O(n) time. Only a handful of integer variables are stored → O(1) space.

E · Edge cases and pitfalls6height = [3, 2, 1] — Descending; the right end is always ≤ left, so we keep resolving the right with rightMax that never exceeds the current bar → 0 water.Explore edge cases

Edge cases handled

height = [3, 2, 1]Descending; the right end is always ≤ left, so we keep resolving the right with rightMax that never exceeds the current bar → 0 water.
height = [5]Single bar; l == r immediately, loop body never runs → 0.
height = [2, 0, 2]leftMax=2 and the right 2 bounds the dip; bar 1 traps 2 units → returns 2.

Pitfalls

Adding water before updating the running max — produces a negative contribution on a new tallest bar.
Advancing the taller side — you'd use a max that isn't yet guaranteed to bound the bar.
Using <= vs < inconsistently between the comparison and the loop condition, risking double counting at the meeting point.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int trap(int[] height) { int l = 0, r = height.length - 1; int leftMax = 0, rightMax = 0; int water = 0; while (l < r) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Updating the max after adding water

If the current bar is a new maximum, water should be 0. Adding before the max update computes a negative value and corrupts the total.

Explore the code comparison

Don't write this

water += left_max - height[l]
left_max = max(left_max, height[l])

Write this instead

left_max = max(left_max, height[l])
water += left_max - height[l]

Advancing the wrong (taller) side

The correctness argument only holds when you process the shorter end; the shorter side's water is bounded by its running max because the far wall is provably taller.

Explore the code comparison

Don't write this

if (height[l] < height[r]) {
    rightMax = Math.max(rightMax, height[r]);
    water += rightMax - height[r];
    r--;
}

Write this instead

if (height[l] < height[r]) {
    leftMax = Math.max(leftMax, height[l]);
    water += leftMax - height[l];
    l++;
}

Nested scans for left/right max

Scanning left and right for every bar recomputes overlapping work — O(n²) and too slow for n up to 2×10⁴ in tight settings.

Explore the code comparison

Don't write this

for i in range(n):
    lmax = max(height[:i+1])
    rmax = max(height[i:])
    water += min(lmax, rmax) - height[i]

Write this instead

# precompute running maxes once, or use two pointers
l, r, left_max, right_max, water = 0, n - 1, 0, 0, 0

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers with leftMax/rightMax; water = min(maxes) − height

Code pattern to memorize

l, r = 0, n-1
leftMax = rightMax = 0
water = 0
while l < r:
    if height[l] < height[r]:
        leftMax = max(leftMax, height[l]); water += leftMax - height[l]; l += 1
    else:
        rightMax = max(rightMax, height[r]); water += rightMax - height[r]; r -= 1

Rules to remember

1Water trapped above a bar = min(maxLeft, maxRight) − height[bar], never negative.
2In the two-pointer version, advance the side with the smaller bar — its trapped water is decided by that side's max alone.
3Update the running max before adding water, so the current bar can't trap negative water.
4The bars at the very ends trap nothing; water needs a taller wall on both sides.
5Prefix/suffix-max arrays (O(n) space) are the clearest baseline — the two-pointer trick removes those arrays.

Use this pattern when

Accumulate a per-index contribution that depends on a left-side and right-side extreme
You can precompute prefix/suffix aggregates, then optimize them away with two pointers
Histogram / elevation-map problems about volume between bars
You need O(1) space and can argue the smaller side is fully resolved

Choose another pattern when

You only pick two lines and ignore the bars between → Container With Most Water
You need the largest single rectangle, not trapped water → monotonic stack (Largest Rectangle)
Bars can be reordered → this is a fixed-position problem

Interview takeaway

Trapping Rain Water is the canonical 'per-index value depends on a left max and a right max' problem. Master the progression prefix/suffix arrays → two running maxes, and the same space-saving move reappears in DP-to-O(1) optimizations everywhere.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPer-index value bounded by a left-max and a right-max. Recognise it for volume-between-bars problems: derive the prefix/suffix-array formula, then collapse to two running maxes with two pointers for O(1) space. Cousin of Container With Most Water.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Container With Most Water
Also two pointers, but you pick exactly two lines for max area instead of summing trapped water.
Largest Rectangle in Histogram
Coming soon
Bars again, but maximize a single rectangle — solved with a monotonic stack.
Trapping Rain Water II
Coming soon
2D elevation map — process cells from the lowest boundary inward with a min-heap.

Same pattern

←

Container With Most Water

Continue · Next problem

Merge Sorted Array

hardArraysLC #42Frequently asked

Trapping Rain Water

LCPractice

Two Pointers · 4 of 30 · 12 min

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

In plain English

Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Note: The dips between taller bars hold 6 units total (classic LeetCode picture).

Example 2

Input: height = [4,2,0,3,2,5]
Output: 9
Note: Between the 4 on the left and 5 on the right, the valley traps 9 units.

Example 3

Input: height = [3, 2, 1]
Output: 0
Note: Strictly descending — no right wall ever rises again, so nothing is trapped.

Constraints

n == height.length
1 ≤ n ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵

Clarifying questions4First question: How much water sits above a single bar?Explore questions

Q1.How much water sits above a single bar?
min(tallest to the left, tallest to the right) − the bar's own height, clamped at zero.
Q2.Do the leftmost and rightmost bars trap water?
No — there's no taller wall on the outside to contain it, so their contribution is zero.
Q3.Can heights be zero or flat?
Yes. Flat or descending terrain traps nothing; the formula naturally yields zero.
Q4.Is O(1) extra space expected?
The prefix/suffix-array solution is O(n) space and clear; the two-pointer solution achieves O(1) and is the target for a hard problem.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Reasoning about water column-by-column with nested scans (O(n²)), or in the two-pointer version advancing the wrong side / updating the max after adding water.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Prefix-Max & Suffix-Max Arrays	`O(n)`	`O(n)`	Say it first — it makes the water formula explicit and is the clearest correct baseline before optimizing space. (Mention the naive O(n²) per-column scan, then improve to this.)	Read
2	Two Pointers — Running Maxes (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want for a hard problem. Phrase it as 'I don't need the whole prefix/suffix arrays — two running maxes and two pointers suffice'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Prefix-Max & Suffix-Max Arrays

TimeO(n)SpaceO(n)

Say it first — it makes the water formula explicit and is the clearest correct baseline before optimizing space. (Mention the naive O(n²) per-column scan, then improve to this.)

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start naive: for each bar, scan left for the tallest bar and right for the tallest bar; water above it is min(those two) − height. That's correct but O(n²).

2Hint 2Explore hint

The two scans recompute the same maxes repeatedly. Precompute them: maxLeft[i] = tallest bar in [0..i], maxRight[i] = tallest bar in [i..n-1].

3Hint 3Explore hint

Then water = sum over i of (min(maxLeft[i], maxRight[i]) − height[i]). Two passes to build the arrays, one pass to sum.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

height = [4, 2, 0, 3, 2, 5]

maxLeft

running max L→R

State[4,4,4,4,4,5]

Final result9

C · Code with teaching comments

Reference implementation previewpublic int trap(int[] height) { int n = height.length; if (n == 0) return 0; int[] maxLeft = new int[n]; int[] maxRight = new int[n];Explore the full code

solution.javaJava

Prefix-Max & Suffix-Max Arrays — reference

3 teaching notes

1
public int trap(int[] height) {
2
    int n = height.length;
3
    if (n == 0) return 0;
4
    int[] maxLeft = new int[n];
5
    int[] maxRight = new int[n];
6
    maxLeft[0] = height[0];
7
    for (int i = 1; i < n; i++) {
8
        // Running max from the left — tallest wall at or before i.
9
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
10
    }
11
    maxRight[n - 1] = height[n - 1];
12
    for (int i = n - 2; i >= 0; i--) {
13
        // Running max from the right — tallest wall at or after i.
14
        maxRight[i] = Math.max(maxRight[i + 1], height[i]);
15
    }
16
    int water = 0;
17
    for (int i = 0; i < n; i++) {
18
        // Water above bar i; non-negative because both maxes ≥ height[i].
19
        water += Math.min(maxLeft[i], maxRight[i]) - height[i];
20
    }
21
    return water;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Three linear passes (build prefix-max, build suffix-max, sum) = O(n) time. Two auxiliary arrays of length n → O(n) space.

E · Edge cases and pitfalls3Computing the maxes with nested scans instead of running maxes — back to O(n²).Explore edge cases

Pitfalls

Computing the maxes with nested scans instead of running maxes — back to O(n²).
Initializing the suffix array left-to-right by mistake.
Forgetting that the result per bar is guaranteed non-negative only because the maxes include the bar itself.

03.2

Approach 2 of 2 · Optimal

Two Pointers — Running Maxes (Optimal)

TimeO(n)SpaceO(1)

The answer they want for a hard problem. Phrase it as 'I don't need the whole prefix/suffix arrays — two running maxes and two pointers suffice'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In the array solution, water at i needs only min(maxLeft[i], maxRight[i]). What if you tracked leftMax and rightMax on the fly with two pointers?

2Hint 2Explore hint

3Hint 3Explore hint

So when height[l] < height[r], update leftMax and add leftMax − height[l], then l++. Otherwise do the symmetric thing on the right with r--.

A · Core idea

Keep two pointers l and r at the ends and two running maxes leftMax, rightMax. At each step compare height[l] and height[r] and process the smaller side.

Why O(n) time and O(1) space. Each element is visited once as a pointer passes it, and the only state is four integers (two pointers, two maxes) plus the accumulator.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

height = [4, 2, 0, 3, 2, 5]

Array state

l=1, r=5

left 2 < right 5; leftMax 4; +2 water

[0]

l ↓

[1]

[2]

[3]

[4]

r ↓

[5]

Current pointerResolved stateNot processed

Final result9

C · Code with teaching comments

solution.javaJava

Two Pointers — Running Maxes (Optimal) — optimal

4 teaching notes

1
public int trap(int[] height) {
2
    int l = 0, r = height.length - 1;
3
    int leftMax = 0, rightMax = 0;
4
    int water = 0;
5
    while (l < r) {
6
        // Left end is shorter → the right side is guaranteed tall enough, so left's
7
        // water is decided by leftMax.
8
        if (height[l] < height[r]) {
9
            // Update the running max BEFORE adding water so the tallest-so-far bar
10
            // traps zero, not negative.
11
            leftMax = Math.max(leftMax, height[l]);
12
            // Commit bar l's trapped water and never revisit it.
13
            water += leftMax - height[l];
14
            l++;
15
        } else {
16
            rightMax = Math.max(rightMax, height[r]);
17
            water += rightMax - height[r];
18
            r--;
19
        }
20
    }
21
    return water;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Edge cases handled

height = [3, 2, 1]Descending; the right end is always ≤ left, so we keep resolving the right with rightMax that never exceeds the current bar → 0 water.
height = [5]Single bar; l == r immediately, loop body never runs → 0.
height = [2, 0, 2]leftMax=2 and the right 2 bounds the dip; bar 1 traps 2 units → returns 2.

Pitfalls

Adding water before updating the running max — produces a negative contribution on a new tallest bar.
Advancing the taller side — you'd use a max that isn't yet guaranteed to bound the bar.
Using <= vs < inconsistently between the comparison and the loop condition, risking double counting at the meeting point.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int trap(int[] height) { int l = 0, r = height.length - 1; int leftMax = 0, rightMax = 0; int water = 0; while (l < r) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Updating the max after adding water

If the current bar is a new maximum, water should be 0. Adding before the max update computes a negative value and corrupts the total.

Explore the code comparison

Don't write this

water += left_max - height[l]
left_max = max(left_max, height[l])

Write this instead

left_max = max(left_max, height[l])
water += left_max - height[l]

Advancing the wrong (taller) side

The correctness argument only holds when you process the shorter end; the shorter side's water is bounded by its running max because the far wall is provably taller.

Explore the code comparison

Don't write this

if (height[l] < height[r]) {
    rightMax = Math.max(rightMax, height[r]);
    water += rightMax - height[r];
    r--;
}

Write this instead

if (height[l] < height[r]) {
    leftMax = Math.max(leftMax, height[l]);
    water += leftMax - height[l];
    l++;
}

Nested scans for left/right max

Scanning left and right for every bar recomputes overlapping work — O(n²) and too slow for n up to 2×10⁴ in tight settings.

Explore the code comparison

Don't write this

for i in range(n):
    lmax = max(height[:i+1])
    rmax = max(height[i:])
    water += min(lmax, rmax) - height[i]

Write this instead

# precompute running maxes once, or use two pointers
l, r, left_max, right_max, water = 0, n - 1, 0, 0, 0

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers with leftMax/rightMax; water = min(maxes) − height

Code pattern to memorize

l, r = 0, n-1
leftMax = rightMax = 0
water = 0
while l < r:
    if height[l] < height[r]:
        leftMax = max(leftMax, height[l]); water += leftMax - height[l]; l += 1
    else:
        rightMax = max(rightMax, height[r]); water += rightMax - height[r]; r -= 1

Rules to remember

1Water trapped above a bar = min(maxLeft, maxRight) − height[bar], never negative.
2In the two-pointer version, advance the side with the smaller bar — its trapped water is decided by that side's max alone.
3Update the running max before adding water, so the current bar can't trap negative water.
4The bars at the very ends trap nothing; water needs a taller wall on both sides.
5Prefix/suffix-max arrays (O(n) space) are the clearest baseline — the two-pointer trick removes those arrays.

Use this pattern when

Accumulate a per-index contribution that depends on a left-side and right-side extreme
You can precompute prefix/suffix aggregates, then optimize them away with two pointers
Histogram / elevation-map problems about volume between bars
You need O(1) space and can argue the smaller side is fully resolved

Choose another pattern when

You only pick two lines and ignore the bars between → Container With Most Water
You need the largest single rectangle, not trapped water → monotonic stack (Largest Rectangle)
Bars can be reordered → this is a fixed-position problem

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Container With Most Water
Also two pointers, but you pick exactly two lines for max area instead of summing trapped water.
Largest Rectangle in Histogram
Coming soon
Bars again, but maximize a single rectangle — solved with a monotonic stack.
Trapping Rain Water II
Coming soon
2D elevation map — process cells from the lowest boundary inward with a min-heap.

Same pattern

←

Container With Most Water

Continue · Next problem

Merge Sorted Array