LeetCode 42 – Trapping Rain Water

Trapping Rain Water is one of the most-asked Hard problems, and the reason it defeats people is that they try to find the puddles. Do not look for puddles. Look at one column at a time and ask how deep the water is there — that question has a one-line answer, and summing it solves the whole thing.

The problem

Given an elevation map where each bar has width 1, compute how much water it traps after rain.

height = [0,1,0,2,1,0,1,3,2,1,2,1]  -> 6

            █
    █░░░░░░██░██
  █░██░█████████
  0102101 3 21 21      ░ = trapped water, 6 units in total

The reframing: per column, not per puddle

Identifying basins means finding their left wall, right wall, and every dip between — fiddly, and it falls apart on nested basins. Instead, fix a single index i and ask: how much water sits directly above it?

Water at i is held in by the tallest bar somewhere to its left and the tallest bar somewhere to its right. The shorter of those two sets the level — water spills over the lower wall — and the bar itself displaces its own height:

water[i] = min(maxLeft[i], maxRight[i]) - height[i]

That formula is the entire problem. It cannot go negative in a valid configuration, because height[i] is itself a candidate for both maxima, so the minimum is at least height[i].

The direct implementation precomputes two arrays in two passes and sums in a third: O(n) time, O(n) space. That is a perfectly good answer and you should offer it first. The follow-up is getting the space to O(1).

Two pointers: why you can decide with half the information

Here is the insight that removes the arrays, and it is worth stating carefully because it looks like sleight of hand.

Walk two pointers inwards, tracking the tallest bar seen so far from each side. At each step, process the side with the shorter bar. If height[lo] < height[hi], then there exists a bar at hi at least that tall to the right of lo — so maxRight[lo] is guaranteed to be at least height[lo], and therefore min(maxLeft, maxRight) at lo is decided entirely by leftMax.

You never learn the true maxRight for that column, and you do not need to. You only need to know it is not the limiting one. That is what buys the O(1) space.

Java

class Solution {
    public int trap(int[] height) {
        int lo = 0, hi = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        while (lo < hi) {
            if (height[lo] < height[hi]) {
                // Something at least this tall exists to the right, so the left
                // wall is the limiting one and leftMax alone decides this column.
                leftMax = Math.max(leftMax, height[lo]);
                water += leftMax - height[lo];
                lo++;
            } else {
                rightMax = Math.max(rightMax, height[hi]);
                water += rightMax - height[hi];
                hi--;
            }
        }

        return water;
    }
}

Update the running maximum before adding the water. Do it after and the current bar is not yet a candidate for its own wall, so a bar taller than everything before it contributes a negative amount. Ordering these two lines wrong is the most common bug in this solution and it does not throw — it just returns a number that is slightly too small.

The empty array needs no guard: hi is -1, the loop never runs, and the answer is 0.

Python

class Solution:
    def trap(self, height: list[int]) -> int:
        lo, hi = 0, len(height) - 1
        left_max = right_max = 0
        water = 0

        while lo < hi:
            if height[lo] < height[hi]:
                left_max = max(left_max, height[lo])    # update BEFORE adding
                water += left_max - height[lo]
                lo += 1
            else:
                right_max = max(right_max, height[hi])
                water += right_max - height[hi]
                hi -= 1

        return water

The prefix-array version

Write this one first if the two-pointer argument does not come to you under pressure. It is a direct transcription of the formula, it is much easier to get right, and O(n) space is rarely disqualifying:

int n = height.length;
if (n == 0) return 0;

int[] maxLeft = new int[n], maxRight = new int[n];

maxLeft[0] = height[0];
for (int i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);

maxRight[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i]);

int water = 0;
for (int i = 0; i < n; i++) water += Math.min(maxLeft[i], maxRight[i]) - height[i];

A correct O(n)-space answer beats a broken O(1)-space one every time. Say "this is O(n) space; there is an O(1) two-pointer version, shall I write it?" and let the interviewer choose.

Complexity

Approach	Time	Space
Scan for each column's walls	`O(n²)`	`O(1)`
Prefix / suffix maxima	`O(n)`	`O(n)`
Monotonic stack	`O(n)`	`O(n)`
Two pointers	`O(n)`	`O(1)`

The stack solution is worth knowing exists because it computes the water horizontally — layer by layer, resolving a basin whenever a bar taller than the stack top arrives — rather than column by column. It is the same family as Valid Parentheses: the stack holds the bars still waiting to be closed off.

The 2-D follow-up

Trapping Rain Water II (407) is the same question on a grid, and the two-pointer trick does not survive the extra dimension — water escapes in four directions, so there is no "shorter side" to reason about. The answer is a min-heap seeded with the border cells, processing lowest first, which is Dijkstra's shape. Naming that is a strong close even if you do not write it.

What the interviewer is checking

That you switch from finding puddles to computing one column at a time.
That you can state min(maxLeft, maxRight) - height[i] and say why the min is there.
That you offer the O(n)-space version rather than stalling on the clever one.
If you write two pointers: that you can justify why the shorter side is safe to process.
That the running maximum updates before the water is added.
Empty array, a strictly increasing array, and a flat array — all trap nothing.