Trapping Rain Water: Think in Columns, Not Pools

Trapping Rain Water is LeetCode #42, one of the most-asked hard problems in existence — and it looks like a physics simulation. Bars, rain, water pooling in the gaps. The first instinct is to find each pool, work out its walls and floor, and sum the geometry. That instinct is the trap.

The unlock is a change of unit: stop thinking about pools and start thinking about columns. The water on top of any single bar is decided by exactly three numbers — the tallest wall anywhere to its left, the tallest wall anywhere to its right, and the bar's own height. See that, and a hard problem collapses into two running-max sweeps and an addition loop.

The problem#

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water the map traps after raining.

The walls of height 2 (index 3) and 3 (index 7) hold a pool between them, and smaller dips catch the rest — 6 units total. Two properties of the setup do a lot of quiet work:

• Every bar has width 1, so the water above a column is just a height difference. No areas, no geometry.
• Water only stays put if both sides have something at least as tall. A wall on one side alone lets everything drain away.

The brute force baseline#

Take the column view literally. For each index, scan left for the tallest bar, scan right for the tallest bar, and the water on top is the shorter of those two walls minus the bar itself.

This is already the right formula — the problem is the rescanning. The tallest-to-the-left of index i differs from the tallest-to-the-left of i − 1 by exactly one comparison, yet this code recomputes it with a full O(n) scan at every index. That's O(n²) — hundreds of millions of comparisons on a 2×10⁴-element input (the LeetCode constraint) for questions earlier passes already answered.

The key insight: precompute the walls once#

Name the redundancy and you've named the fix. The inner loops compute a running max — and running maxes over every prefix of an array take one pass, total, not one pass per element.

So flip the work order:

1. One left-to-right sweep builds maxL[], where maxL[i] = tallest bar from index 0 through i. The recurrence is one comparison: maxL[i] = max(maxL[i−1], arr[i]).
2. One right-to-left sweep builds maxR[], where maxR[i] = tallest bar from i through the end. Same recurrence, mirrored.
3. One final pass applies the column formula: water at i is min(maxL[i], maxR[i]) − arr[i].

The min is the physics of the whole problem: water rises to the level of the shorter of the two best walls, because that's where it spills over. This is the prefix-max pattern — "remember the best so far", paid once as O(n) memory so the main loop reads each answer in O(1).

The optimal solution#

This is exactly the algorithm the visualizer traces, with one neat compression: it fills maxL (front to back) and maxR (back to front) inside a single loop using the mirrored index n − 1 − i.

Three details worth pausing on:

• Base cases first. The leftmost bar's best left wall is itself (maxL[0] = arr[0]); the rightmost bar's best right wall is itself (maxR[n-1] = arr[n-1]). Everything else derives from these.
• The mirrored fill works because of write order. When iteration i writes maxR[n-1-i], it reads maxR[n-i] — the cell one to its right, which the previous iteration (or the base case) already filled. Both arrays complete in one loop.
• The clamp Math.max(waterTrapped, 0). Because both maxes include arr[i] itself, the subtraction never goes negative here — the clamp is a free safety net. It becomes load-bearing the moment you switch to the (also common) convention where the maxes exclude the current bar.

Walkthrough: arr = [4, 2, 0, 3, 2, 5]#

This is the "Two valleys" test case from the visualizer. After the build loop, the prefix arrays look like this:

Now the water pass reads one entry from each array per index:

Return 9. Notice what the column view did to the geometry: physically this terrain holds two irregular pools separated by the height-3 bar, but the code never had to know that. The water line across the basin is 4 — pinned by the left wall — and each column independently measures its gap up to that line. The bar at index 3 pokes into the pool and still traps 1 unit above itself.

Complexity#

Reach for the prefix-array version first: it's the direct translation of the insight, and every intermediate value is inspectable — exactly why the visualizer teaches it. The two-pointer refinement (covered in the FAQ) squeezes space to O(1) by noticing you never need both exact walls, only the shorter one.

Common mistakes#

• Reasoning about pools instead of columns. Pool boundaries merge, nest, and overlap — per-pool bookkeeping is genuinely hard. The per-column decomposition is the entire trick.
• Letting neighbors decide the water level. A bar of height 0 next to a bar of height 1 can still hold 4 units if the tall walls are far away. The maxes are global to each side, not local.
• Flipping the mirrored index in the build loop. maxR[n-1-i] must derive from maxR[n-i], the already-filled cell to its right. Read the wrong side and you hit an unfilled slot — Math.max(undefined, x) is NaN, which silently poisons every cell after it.
• Dropping the clamp after changing conventions. If your maxes exclude the current bar, min − arr[i] goes negative on every local peak, and those negatives quietly shrink the total.
• Confusing this with Container With Most Water. That problem wants the single best pair of walls; this one wants the sum over every column. Returning a max instead of accumulating is a classic mix-up under pressure.

Where this pattern shows up next#

Trapping Rain Water is the capstone of the two-pointers track — the earlier problems build the exact reflexes this one assumes:

• Two Sum — where the track starts: replacing a nested rescan with remembered state, the same redundancy-killing move the prefix arrays make here.
• Two Sum II - Input Array Is Sorted — converging left/right pointers with a spill-side argument; the O(1)-space variant of this problem uses the identical skeleton.
• Is Subsequence — forward two pointers in their simplest form, one per sequence.
• Find the Index of the First Occurrence in a String — sliding an aligned scan across an array, another shape of the same pointer discipline.

You can also step through it interactively and watch both prefix arrays fill in from opposite ends of the same loop, then see each column's water get claimed one bar at a time.

FAQ#

Can Trapping Rain Water be solved in O(1) space?#

Yes — with two pointers and two running maxes. Keep l and r at the ends, plus lmax and rmax for the best wall seen from each side. Whichever end is currently shorter gets processed and moved inward: update that side's running max, add runningMax − height to the answer, advance the pointer. The invariant: if arr[l] < arr[r], the right side guarantees a wall at least as tall as anything the left has seen, so lmax alone decides the water at l. One watch-out — update the running max before adding water, or short bars produce negative contributions.

Why is the water level min(maxL[i], maxR[i])?#

Because water escapes over the shorter boundary. Even if one side has a wall of height 100, water above a column can only rise to the height of the other side's best wall before spilling out that way. The shorter of the two best walls is the bottleneck, so the trapped amount at index i is min(maxL[i], maxR[i]) − arr[i] — and a taller wall past that level adds nothing.

Is the prefix max solution dynamic programming?#

Yes — this is usually catalogued as the DP solution to Trapping Rain Water. maxL[i] = max(maxL[i−1], arr[i]) is a textbook recurrence: each subproblem (best wall up to index i) is answered in O(1) from the previous subproblem's answer, and results are memoized in an array. It's DP at its friendliest — one dimension, one comparison per state.

What is the time complexity of Trapping Rain Water?#

The prefix max solution runs in O(n) time and O(n) space: one loop builds both prefix arrays and a second loop sums the water, with constant work per index. The brute force is O(n²) time with O(1) space because it rescans both directions for every bar. The two-pointer variant keeps O(n) time and cuts space to O(1).

Why does maxL[i] include the current bar itself?#

Both conventions work, but including arr[i] in its own maxes has a tidy consequence: min(maxL[i], maxR[i]) can never be smaller than arr[i], so the water formula never goes negative and walls naturally compute to 0 water. If your maxes exclude the current bar — the other common convention — every local peak produces a negative difference, and you must clamp each term to 0 before adding it. Pick one convention and stay consistent.