Trapping Rain Water

This is the hard problem of the section and one of the most famous interview questions. It rewards a clear formula first and clever pointer movement second. The two-pointer version is short, but you can only defend it if you can say why settling the lower side is always correct — so most of this lesson is about that argument.

The problem

You are given a list of non-negative integers. Each value is the height of a bar of width 1, placed side by side. After rain, water collects in the dips between bars. Return the total units of water held.

• [4, 1, 3, 0, 2, 5, 1, 2] → 11. Per bar, from left to right: 0, 3, 1, 4, 2, 0, 1, 0.
• [3, 0, 2, 0, 4] → 7. Per bar: 0, 3, 1, 3, 0.

Constraints: 1 ≤ len(heights) ≤ 10⁵; 0 ≤ heights[i] ≤ 10⁵.

Clarifying questions

• Does water spill off the two ends? Yes — there are no walls beyond the first and last bars, so those bars hold nothing above them.
• Can heights be zero? Yes. A zero bar can hold the most water.
• Width of each bar? 1, so water above a bar is just a height difference.

Approach 1: the simple way

Water above bar i rises to the level of the shorter of two walls: the tallest bar at or left of i, and the tallest bar at or right of i. Subtract the bar itself.

water[i] = min(tallest on the left, tallest on the right) − heights[i]

Including bar i in both maximums keeps the result from going negative. The simple code scans both directions for every bar:

1def trap_brute(heights: list[int]) -> int:2    """For each bar, scan left and right for the tallest walls."""3    total = 04    for i in range(len(heights)):5        left_max = max(heights[: i + 1])6        right_max = max(heights[i:])7        total += min(left_max, right_max) - heights[i]8    return total

Time O(n²), space O(n) — each slice copies up to n values. At n = 10⁵ that is about 10¹⁰ operations. The repeated work is obvious: bar i + 1 rescans almost exactly what bar i just scanned.

The key insight, part 1: remember the maximums

The tallest bar to the left of i is the tallest to the left of i − 1, or bar i itself. So compute all left maximums in one pass from the left, and all right maximums in one pass from the right. Then each bar's water is one min and one subtraction.

Approach 2: prefix and suffix maximums

1def trap_prefix(heights: list[int]) -> int:2    """Precompute the tallest bar to the left and to the right of every index."""3    n = len(heights)4    if n == 0:5        return 06    left_max = [0] * n7    right_max = [0] * n8    left_max[0] = heights[0]9    for i in range(1, n):10        left_max[i] = max(left_max[i - 1], heights[i])11    right_max[n - 1] = heights[n - 1]12    for i in range(n - 2, -1, -1):13        right_max[i] = max(right_max[i + 1], heights[i])14    return sum(min(left_max[i], right_max[i]) - heights[i] for i in range(n))

On [4, 1, 3, 0, 2, 5, 1, 2]:

Total 11. Time O(n) — three passes. Space O(n) — two extra lists. This is a strong answer. The follow-up is always: "can you do it in O(1) space?"

The key insight, part 2: you only need the smaller wall

Look again at min(left_max, right_max). You need the exact value of only the smaller of the two. Now run one pointer from each end, each carrying the tallest bar it has seen so far: left_max over heights[0..left], right_max over heights[right..n−1].

Suppose left_max < right_max. Consider the next bar on the left side. Its true left maximum is left_max (updated with the bar itself) — the pointer has seen everything to its left. Its true right maximum is at least right_max, because right_max is the height of a bar somewhere to its right. That is already bigger than left_max. So the min is left_max, whatever the unseen middle holds. The water at that bar is settled without knowing the rest of the array.

The mirror argument settles the right side when right_max ≤ left_max. So at each step, advance the side with the smaller running maximum, and add its water.

Approach 3: two pointers, O(1) space

1def trap(heights: list[int]) -> int:2    """Total water trapped between the bars, in O(1) extra space."""3    if not heights:4        return 05    left, right = 0, len(heights) - 16    left_max, right_max = heights[left], heights[right]7    trapped = 08    while left < right:9        if left_max < right_max:10            left += 111            left_max = max(left_max, heights[left])12            trapped += left_max - heights[left]     # never negative13        else:14            right -= 115            right_max = max(right_max, heights[right])16            trapped += right_max - heights[right]17    return trapped

Dry run on [4, 1, 3, 0, 2, 5, 1, 2]. Start: left = 0, right = 7, left_max = 4, right_max = 2.

Now left = right = 5 and the loop stops: 11, matching the table from Approach 2. Every bar's water was added exactly once, from whichever side settled it.

Complexity. Each step moves one pointer inward: O(n) time, O(1) space.

Edge cases

• Fewer than three bars. Nothing can be trapped; the loop adds 0s (and an empty list returns 0 at once).
• Rising or falling heights, such as [1, 2, 3]. No dips; every addition is 0.
• A single deep dip, such as [2, 0, 2]. Returns 2.
• Equal running maximums. The else branch settles the right side, which the mirror argument allows.

All three approaches agreed on 300 random lists of up to 12 heights between 0 and 6, plus the empty list and the examples above.

Follow-ups

• "Solve it with a stack." A monotonic decreasing stack of indices fills water layer by layer when a taller bar arrives: also O(n) time, O(n) space. The Stacks section covers the technique.
• "The bars form a 2-D grid of heights." Two pointers no longer work. Use a min-heap seeded with the border cells and grow inward from the lowest wall: O(mn log(mn)).
• "Return the water above each bar." Approach 2 already has it; in Approach 3, write each trapped += amount into an output list.