4.5.5 — Trapping Rain Water

LeetCode 42 · Hard · ★ Blind 75

The problem

Each number is the height of a bar. After rain, how much water is trapped between the bars?

height = [0,1,0,2,1,0,1,3,2,1,2,1]   →  6

Up to 20,000 bars.

The pattern

Do not think about the whole shape at once. Think about one position at a time and ask how deep the water is directly above it.

Water sits above position i up to the level of the lower of the two walls around it — the tallest bar somewhere to its left, and the tallest bar somewhere to its right. Water above that level would spill over the shorter side.

\text{water}[i] = \min(\text{leftMax},\, \text{rightMax}) - \text{height}[i]

If that comes out negative, the bar itself is taller than the walls and holds no water, so the answer there is 0.

Two facts make this concrete:

• The first and last bars always hold nothing, because one side has no wall.
• leftMax includes height[i] itself, so a bar that is its own left maximum gives exactly zero water. That is why no separate check is needed.

Once you have this formula, the whole problem is how do I get leftMax and rightMax cheaply.

The water level over a dip is the shorter of the two surrounding peaks, and the bar's own height is subtracted from it.

Solution 1 — precompute both maxima

The straightforward version. Two passes fill two arrays, then one pass adds up the water.

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max = [0] * n
        right_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

O(n) time, O(n) space.

This is exactly 4.4.7 Product of Array Except Self with max instead of ×. Two passes in opposite directions, each carrying a running value, then combined. Write this version first — it is easy to get right and easy to explain.

Solution 2 — two pointers, O(1) space

The clever version. It rests on one observation:

You do not need to know the exact right maximum. You only need to know which side is smaller.

Keep left_max and right_max as running values from the two ends. Suppose left_max < right_max. Then for the left pointer, min(left_max, rightMax_true) is left_max — because the true right maximum is at least right_max, which is already bigger than left_max. So the water above the left pointer is settled, and you can compute it without ever seeing the rest of the array.

That is the whole trick: process whichever side has the smaller wall, because that side's answer is already fully determined.

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        left_max, right_max = height[l], height[r]
        trapped = 0

        while l < r:
            if left_max < right_max:
                l += 1
                if height[l] >= left_max:
                    left_max = height[l]        # a new wall
                else:
                    trapped += left_max - height[l]
            else:
                r -= 1
                if height[r] >= right_max:
                    right_max = height[r]
                else:
                    trapped += right_max - height[r]

        return trapped

TypeScript

function trap(height: number[]): number {
  if (height.length === 0) return 0;

  let l = 0, r = height.length - 1;
  let leftMax = height[l], rightMax = height[r];
  let trapped = 0;

  while (l < r) {
    if (leftMax < rightMax) {
      l++;
      if (height[l] >= leftMax) leftMax = height[l];
      else trapped += leftMax - height[l];
    } else {
      r--;
      if (height[r] >= rightMax) rightMax = height[r];
      else trapped += rightMax - height[r];
    }
  }

  return trapped;
}

Two details in the shape of this code are deliberate.

The pointer moves before the bar is examined. That is what skips index 0 and the last index automatically, and those are the two positions that can never hold water. No boundary check is needed.

There is no max(..., 0) anywhere. Once you are in the else branch you already know height[l] < left_max, so the subtraction cannot go negative. Clamping it would be dead work.

Trace

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], answer 6.

l	r	left_max	right_max	side moved	water added
0	11	0	1	left, height[1]=1 ≥ 0 → new wall	0
1	11	1	1	right, height[10]=2 ≥ 1 → new wall	0
1	10	1	2	left, height[2]=0 < 1	+1
2	10	1	2	left, height[3]=2 ≥ 1 → new wall	0
3	10	2	2	right, height[9]=1 < 2	+1
3	9	2	2	right, height[8]=2 ≥ 2 → new wall	0
3	8	2	2	right, height[7]=3 ≥ 2 → new wall	0
3	7	2	3	left, height[4]=1 < 2	+1
4	7	2	3	left, height[5]=0 < 2	+2
5	7	2	3	left, height[6]=1 < 2	+1
6	7	2	3	pointers meet	—

Total 6. ✓

Complexity

O(n) time, O(1) space. Each pointer moves only inwards, so together they take n steps.

Solution 3 — a monotonic stack

There is a third answer, filling the water horizontally layer by layer instead of vertically column by column. Keep a stack of decreasing bar heights; when a taller bar arrives, it closes off a basin, and you compute that basin's water from the popped bar, the new bar, and whatever is now on top of the stack.

O(n) time and O(n) space, so it is worse than solution 2 here. It is worth knowing because the same machinery solves Largest Rectangle in Histogram, and it is built properly in 4.8.

Edge cases

Empty array and a single bar both give 0. A strictly increasing or strictly decreasing array gives 0, because one side never has a wall. A flat array gives 0.

What the interviewer will push on

"Why can you use left_max without knowing the true right maximum?" Because when left_max < right_max, the true right maximum is at least right_max, so the min is left_max regardless of what else is on the right. This is the question the problem exists to ask.

"Show me the O(n)-space version first." Do that anyway. Explain the two-array version, then say you can drop the arrays by tracking which side is smaller. Jumping straight to the pointer version and stumbling is a worse outcome than building up to it.

"What if the bars had width, or the input were 2-D?" The 2-D version is Trapping Rain Water II, and it is a genuinely different problem: you process cells from the lowest boundary inwards using a min-heap, because in two dimensions water escapes through the lowest point of the whole rim, not the lower of two sides. Naming that is a strong answer. Chapter 4.17.

One thing to volunteer: say the per-position formula out loud before writing anything. "The water above position i is min(leftMax, rightMax) - height[i]." Everything else follows from it, and candidates who start coding without it usually end up lost.

Next: 4.6 keeps two pointers but sends both forwards only, with a rule for when to shrink — the pattern for every "longest or shortest stretch satisfying a condition" problem.