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.

Constraints:

• The heights are non-negative integers.
• The width of each bar is exactly 1.

Plain English: You have a 2D side-view of a terrain made of blocks of width 1. It rains. Water pools in the valleys between the blocks. How many blocks of water total will be trapped?

The naive approach

The brute-force way is to directly follow the formula for every single position i. For a bar at index i, you run a loop to its left to find the max height, and you run a loop to its right to find the max height.

• Why it fails: For each of the n bars, you scan up to n bars. That's n \times n = O(n^2) time. With 20,000 bars, 20,000^2 = 400 million operations. This will likely TLE. We are recalculating the maxes over and over.

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 ELI5 Analogy: Imagine you're standing in a valley. You want to know how deep the water will get exactly where you are standing. You look to your left and see a mountain 10 feet tall. You look to your right and see a mountain 50 feet tall. Because water levels out, it can only fill up to the top of the shorter mountain before spilling over. So, the water will be exactly 10 feet deep (minus your own height). The entire trick to this problem is just doing this logic efficiently for every spot.

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.

Code Walkthrough

• left_max, right_max = height[l], height[r]: Initialize the maximums with the extreme left and right bars.
• if left_max < right_max:: This is the core logic. If the left wall is shorter than the right wall, we know the bottleneck for the next left bar is guaranteed to be left_max. The actual right wall could be even bigger than right_max, but it doesn't matter because left_max is already strictly smaller and sets the ceiling.
• l += 1: We move the left pointer inwards to process a new bar.
• if height[l] >= left_max:: If this new bar is taller than our recorded left_max, it can't hold any water (it sticks out). Instead, it becomes the new left_max for the bars further in.
• else: trapped += left_max - height[l]: Since the new bar is shorter than left_max, it forms a puddle. The amount of water is exactly left_max - height[l].

Let's derive the complexity of this two-pointer approach:

• Time Complexity: O(n). l starts at 0 and r starts at the end. In every single step of the while loop, we strictly move exactly one pointer (l += 1 or r -= 1). They never move backwards. They meet after exactly n-1 steps. All operations inside the loop are basic math and comparisons (O(1)).
• Space Complexity: O(1). We only maintain a few variables (l, r, left_max, right_max, trapped), regardless of how large the height array is.

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.