LeetCode 42 Trapping Rain Water: Four Approaches, Fully Dry-Run

Trapping Rain Water is LeetCode's most famous Hard problem and one of the most frequently reported hard questions in interviews at Amazon, Google, Microsoft, Goldman Sachs, Flipkart and many others. It is a perfect interview problem because it has a clear ladder: a brute force anyone can write, an O(n) solution once you see one formula, and an O(1)-space version that requires a genuine argument. This walkthrough climbs that ladder with full dry runs, and every implementation has been checked against the brute force on thousands of random inputs.

The Trapping Rain Water Problem

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.

Example: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] traps 6 units. Another: [4, 2, 0, 3, 2, 5] traps 9.

Clarify before solving: heights are non-negative integers; the edges of the array spill water (nothing beyond index 0 or n-1 holds it); n can be up to 2 × 10⁴ on LeetCode, and empty input returns 0.

The Core Insight: Water Depends on Two Maxima

Think about one column at a time. Water above index i rises until it would spill over the lower of the two "walls" around it: the tallest bar somewhere to its left, and the tallest bar somewhere to its right. So:

Applied to the example, per index:

Sum of the last row: 1 + 1 + 2 + 1 + 1 = 6.

Approach 1: Brute Force, O(n²)

For every index, scan left for the maximum and right for the maximum.

def trap_brute(height):
    n = len(height)
    water = 0
    for i in range(n):
        left_max = max(height[:i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - height[i]
    return water

O(n²) time (each index scans up to n bars), O(1) extra space conceptually (the Python slices copy, so write explicit loops if the interviewer cares). At n = 2 × 10⁴ that is about 4 × 10⁸ steps, too slow. The waste is obvious: the left maximum for i+1 is just max(leftMax(i), height[i+1]), yet we recompute it from scratch.

Approach 2: Prefix and Suffix Maximum Arrays, O(n)

Compute maxLeft in one left-to-right pass and maxRight in one right-to-left pass, then apply the formula. This is the same "precompute a running aggregate" idea as prefix sums, with max instead of plus.

public static int trapPrefix(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    int[] left = new int[n], right = new int[n];
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
    return water;
}

def trap_prefix(height):
    n = len(height)
    if n == 0:
        return 0
    left = [0] * n
    right = [0] * n
    left[0] = height[0]
    for i in range(1, n):
        left[i] = max(left[i - 1], height[i])
    right[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right[i] = max(right[i + 1], height[i])
    return sum(min(left[i], right[i]) - height[i] for i in range(n))

O(n) time, O(n) space. The table in the previous section is exactly this algorithm's state. If you are nervous in an interview, write this one first: it is hard to get wrong, it is already optimal in time, and it sets up the two-pointer optimisation naturally ("can we avoid storing both arrays?").

Approach 3: Monotonic Stack, Filling Water Layer by Layer

A completely different view: instead of computing water per column, compute it per horizontal layer of each basin. Keep a stack of indices whose heights are non-increasing. When a bar taller than the stack top arrives, the top is the bottom of a basin, the next element down is its left wall, and the current bar is its right wall. The water in that layer is width × (min(leftWall, rightWall) - bottom).

int trapStack(const vector<int>& h) {
    stack<int> st;                       // indices, heights non-increasing
    int water = 0;
    for (int i = 0; i < (int)h.size(); i++) {
        while (!st.empty() && h[st.top()] < h[i]) {
            int bottom = st.top();
            st.pop();
            if (st.empty()) break;       // no left wall: water spills
            int left = st.top();
            int width = i - left - 1;
            int bounded = min(h[left], h[i]) - h[bottom];
            water += width * bounded;
        }
        st.push(i);
    }
    return water;
}

def trap_stack(height):
    stack = []          # indices, heights non-increasing from bottom to top
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], h) - height[bottom]
            water += width * bounded
        stack.append(i)
    return water

Stack dry run on the example

Look at i = 7: the basin between bars 3 and 7 is filled in two layers. The first pop (index 6, height 1, sitting on index 4 with height 1) adds nothing because the layer is zero-height. The second pop (index 4) fills the layer from height 1 up to 2 across three columns (4, 5, 6). The bottom layer at index 5 was already filled when i = 6 arrived. Layers, not columns.

Each index is pushed once and popped at most once, so the while loop is amortised O(1): O(n) time, O(n) space in the worst case (a strictly decreasing array). The equality case does not matter: with <, equal bars stay on the stack and form zero-height layers. This stack pattern is the same one behind Largest Rectangle in Histogram; see the monotonic stack guide.

Approach 4: Two Pointers in O(1) Space

The prefix approach needs both maxima for every index. The two-pointer approach notices that you only need the smaller of them, and you can know which one is smaller without computing the other exactly.

Keep lo and hi at the two ends, with running leftMax (max of height[0..lo]) and rightMax (max of height[hi..n-1]). At each step, process the side with the shorter bar:

public static int trap(int[] height) {
    int lo = 0, hi = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (lo < hi) {
        if (height[lo] < height[hi]) {
            leftMax = Math.max(leftMax, height[lo]);
            water += leftMax - height[lo];     // left side is the binding wall
            lo++;
        } else {
            rightMax = Math.max(rightMax, height[hi]);
            water += rightMax - height[hi];    // right side is the binding wall
            hi--;
        }
    }
    return water;
}

int trap(const vector<int>& h) {
    int lo = 0, hi = (int)h.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (lo < hi) {
        if (h[lo] < h[hi]) {
            leftMax = max(leftMax, h[lo]);
            water += leftMax - h[lo];
            lo++;
        } else {
            rightMax = max(rightMax, h[hi]);
            water += rightMax - h[hi];
            hi--;
        }
    }
    return water;
}

def trap(height):
    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])
            water += left_max - height[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            water += right_max - height[hi]
            hi -= 1
    return water

Two-pointer dry run

The pointers meet at index 7 (the tallest bar, which never holds water). Total 6. Notice the per-index additions match the "water" row of the formula table exactly; two pointers just computes the same numbers in a different order.

Why the Two-Pointer Approach Is Correct

This is the part interviewers actually test. Suppose height[lo] < height[hi] and we are about to process lo.

1. leftMax is exact for lo. It is the maximum of height[0..lo], which we have fully scanned.
2. The true maxRight[lo] is at least height[hi], since hi is to the right of lo.
3. leftMax ≤ maxRight[lo]. Invariant: every time lo advanced, it was because height[lo] < height[hi] for the hi at that moment, and hi only moves past bars that are not taller than some bar on the left side (the else-branch runs when height[lo] >= height[hi]). So the largest bar seen on the left so far never exceeds the bar currently at hi, or one to its right. Hence leftMax ≤ max(height[hi..n-1]) ≤ maxRight[lo].
4. So min(maxLeft[lo], maxRight[lo]) = leftMax, and the water at lo is exactly leftMax - height[lo]. The symmetric argument handles the right side.

An easy way to say it in an interview: "I process the shorter side because a taller bar is guaranteed on the other side, so this side's water is limited only by its own running max, which I know exactly."

Comparing the Four Approaches

A nuance worth mentioning: the stack approach processes bars strictly left to right, so it works when heights arrive as a stream and you cannot see the right end. Two pointers needs random access to both ends. That is a good answer to "which would you use if the data came from a stream?"

Trapping Rain Water II: The 2D Version (LeetCode 407)

Now the elevation map is an m × n grid and water can escape in four directions. The 1D idea "the shorter wall bounds the water" generalises: water in a cell is bounded by the lowest point on the boundary of the region enclosing it. Process cells from the outside in with a min-heap, always expanding from the lowest boundary cell, like Dijkstra:

import heapq

def trap_rain_water_2d(height_map):
    if not height_map or not height_map[0]:
        return 0
    m, n = len(height_map), len(height_map[0])
    visited = [[False] * n for _ in range(m)]
    heap = []
    for r in range(m):
        for c in range(n):
            if r in (0, m - 1) or c in (0, n - 1):      # outer boundary
                heapq.heappush(heap, (height_map[r][c], r, c))
                visited[r][c] = True
    water = 0
    while heap:
        h, r, c = heapq.heappop(heap)                    # lowest wall so far
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                water += max(0, h - height_map[nr][nc])
                heapq.heappush(heap, (max(h, height_map[nr][nc]), nr, nc))
    return water

On LeetCode's examples this returns 4 and 10. Time O(mn log(mn)), space O(mn). Why it works: when the lowest boundary level is h, any unvisited neighbour can hold water up to h, because every other escape path passes through a boundary at least as high. The pushed level max(h, height) represents the new effective wall. Note that the 1D two-pointer trick does not extend to 2D, and candidates who try "min of max in four directions" get wrong answers, since water can flow around obstacles.

Related Problems and How They Differ

• Container With Most Water (LC 11): choose two lines, maximise the rectangle between them; inner bars are ignored. Also two pointers moving the shorter side, but you maximise one area instead of summing columns.
• Largest Rectangle in Histogram (LC 84): the same monotonic stack, popping when a shorter bar arrives, to find each bar's maximal width.
• Pour Water (LC 755): simulation of droplets; uses the same "lowest reachable point" thinking.
• Product of Array Except Self (LC 238): the same prefix-from-left, suffix-from-right precomputation with a product; see the walkthrough.
• Best Time to Buy and Sell Stock (LC 121): the running-maximum/minimum idea in its simplest form.

How Trapping Rain Water Is Asked in Interviews

A strong performance usually follows this script:

1. Clarify: non-negative heights, width 1, edges spill, empty input returns 0.
2. Derive the formula from one column, with a tiny example, before any code.
3. Mention brute force and its O(n²) cost, then name the waste (recomputing maxima).
4. Code prefix/suffix arrays or go straight to two pointers if confident.
5. Optimise space to O(1) and give the "shorter side is bounded by its own max" argument.
6. Dry run on [4, 2, 0, 3, 2, 5] (answer 9) or the standard example, plus edge cases: fewer than 3 bars (0), strictly increasing or decreasing (0), all equal (0).

Follow-ups to expect: "do it in one pass" (two pointers already is), "what if heights stream in" (stack), "2D version" (heap), "what if bars can have different widths" (weight each column's water by its width; the formula is unchanged), and "return the water per index" (store additions in an array). Red flags: memorised two-pointer code with no explanation, or confusing it with Container With Most Water. More two-pointer reasoning practice is in the two pointers guide.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.