Trapping Rain Water (LeetCode #42)

Trapping Rain Water asks how much water remains between elevation bars after rain. Each column can hold water only up to its shorter boundary: the tallest bar seen on its left or right. The interesting part is proving when those two boundaries are known, then adding every column's non-negative depth.

How trapping rain water works

For an index i, let left_max[i] be the tallest bar from the start through i, and let right_max[i] be the tallest bar from i through the end. The water above that column is:

min(left_max[i], right_max[i]) - height[i]

The current bar is included in both maxima, so this value cannot be negative. A taller wall on only one side is not enough: water spills over the shorter boundary.

The Prefix Max approach makes the proof literal. It builds both arrays, then applies the formula to every column. This takes linear time and linear extra space.

The Two Pointers approach keeps only four values: left, right, left_max, and right_max.

Why the smaller side is final

Settle the side with the smaller running maximum. Suppose left_max <= right_max.

The scan has already seen a bar on the right whose height is right_max. That known wall is at least as tall as left_max, so the current left column is enclosed up to left_max. Nothing hidden between the pointers can undo that fact: another bar may raise the right wall or become an interior pillar, but it cannot remove the wall already seen. Water also cannot rise above left_max, because it would spill over the left boundary.

So the left column's final depth is left_max - height[left]. Settle it and move left inward. When right_max < left_max, the same argument works from the right. Each move permanently settles one column.

Trapping rain water step by step

The default animation uses height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] and the Two Pointers approach.

1. Start at columns 0 and 11. Their running maxima are 0 and 1, so settle the left column with depth 0.
2. Columns 1 and 2 are also settled from the left. Column 2 receives 1 - 0 = 1 unit.
3. At column 3, left_max rises to 2 while right_max is still 1. The right side is now the smaller boundary, so column 11 settles with depth 0.
4. Column 10 raises right_max to 2. With equal boundaries, the trace settles from the left: columns 3, 4, 5, and 6 add 0, 1, 2, and 1 units. The running total reaches 5.
5. Column 7 raises left_max to 3, making the right boundary smaller again. Columns 10, 9, and 8 add 0, 1, and 0 units.
6. Only column 7 remains. Equal maxima make the left branch settle it with depth 0. The final total is 6.

Switch to Prefix Max to inspect the same input from another angle. Its left rail becomes [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]; its right rail becomes [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]. Applying the formula produces depths [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0], which also sum to 6.

Time and space complexity

Both animated approaches do constant work per column: Prefix Max makes three linear passes, and Two Pointers does constant work for each column it retires. The input editor is capped at 14 bars so the full state stays legible; that is a display limit, not an algorithmic one.

This proof shape transfers to Container With Most Water: compare two known boundaries, then move the smaller one because the larger boundary cannot rescue it. The details differ there—it uses the current endpoint heights, not running maxima. Prefix maxima are also a general preprocessing pattern when many later queries need the best boundary seen from each direction.

Edge cases

• Fewer than three bars cannot enclose water.
• An empty map, flat plateau, or monotone slope traps zero water.
• Equal running maxima are safe: this implementation settles the left side on a tie.
• Zero-height bars are ordinary columns, not missing data. Deep basins can hold several units above one index.
• The first and last columns never hold water because each lacks a wall on one side.

Common mistakes

• Using max(left_max, right_max) instead of min(...) invents water above the shorter wall.
• Comparing only height[left] and height[right] while computing depth from stale maxima mixes two different invariants.
• Moving a pointer before recording the current column skips that column or charges its water to the wrong index.
• Forgetting to update the running maximum before subtracting can produce a negative depth.
• Treating equal maxima as a special deadlock can stall the loop. A consistent tie rule is enough.