Trapping Rain Water

This problem appears in top-tier tech interviews at Google, Amazon, and Meta with remarkable frequency. It tests your ability to reason about spatial relationships in arrays and rewards you for knowing multiple solution strategies. The progression from brute force to optimal reveals how algorithmic thinking matures.

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

Example:

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6

Here is a visual representation:

        █
    █ ~ ~ ~ █ █ ~ █
  █ ~ █ █ ~ █ █ █ █ █
  0 1 0 2 1 0 1 3 2 1 2 1

  ~ represents trapped water
  █ represents elevation bars

Water fills the gaps between bars, bounded by the tallest bars on either side. At index 2, the tallest bar to the left is 1, the tallest to the right is 3. Water level at index 2 is min(1, 3) - 0 = 1. At index 5, leftMax is 2, rightMax is 3, so water is min(2, 3) - 0 = 2.

Key Insight

The water trapped at any position i depends on exactly two values:

maxLeft[i] — the tallest bar to the left of i (inclusive)
maxRight[i] — the tallest bar to the right of i (inclusive)

The water level at position i equals min(maxLeft[i], maxRight[i]) - height[i]. If this value is negative, no water is trapped there.

The bottleneck is always the shorter side. A bar 10 units tall on the left does nothing if the tallest bar on the right is only 3 units — water overflows at height 3.

This single insight drives every solution below. The four approaches differ only in how efficiently they compute maxLeft and maxRight.

Approach 1: Brute Force — O(n²) Time, O(1) Space

The most direct translation of the key insight: for each position, scan left to find the maximum height, scan right to find the maximum height, and compute the trapped water.

public int trap(int[] height) {
    int n = height.length;
    int totalWater = 0;

    for (int i = 0; i < n; i++) {
        // Find the tallest bar to the left (including position i)
        int maxLeft = 0;
        for (int j = 0; j <= i; j++) {
            maxLeft = Math.max(maxLeft, height[j]);
        }

        // Find the tallest bar to the right (including position i)
        int maxRight = 0;
        for (int j = i; j < n; j++) {
            maxRight = Math.max(maxRight, height[j]);
        }

        // Water at position i is bounded by the shorter side
        totalWater += Math.min(maxLeft, maxRight) - height[i];
    }

    return totalWater;
}

Why it works: This directly implements the formula. For each bar, you exhaustively find both boundaries.

Why it’s slow: For each of the n positions, you scan up to n elements in each direction. The nested loops produce O(n²) time. In an interview, present this approach first to show you understand the problem, then immediately say: “This recomputes maxLeft and maxRight from scratch at every position. We can precompute them.”

Complexity:

Time: O(n²) — two inner loops per outer iteration
Space: O(1) — no auxiliary data structures

Approach 2: Dynamic Programming — O(n) Time, O(n) Space

The brute force redundantly recomputes maximum heights. Pre-computing two arrays — maxLeft[] and maxRight[] — eliminates the repeated work.

public int trap(int[] height) {
    int n = height.length;
    if (n <= 2) return 0;  // Need at least 3 bars to trap water

    // maxLeft[i] = tallest bar from index 0 to i
    int[] maxLeft = new int[n];
    maxLeft[0] = height[0];
    for (int i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
    }

    // maxRight[i] = tallest bar from index i to n-1
    int[] maxRight = new int[n];
    maxRight[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i + 1], height[i]);
    }

    // Compute total trapped water
    int totalWater = 0;
    for (int i = 0; i < n; i++) {
        totalWater += Math.min(maxLeft[i], maxRight[i]) - height[i];
    }

    return totalWater;
}

How the precomputation works:

For the input [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

index:    0  1  2  3  4  5  6  7  8  9  10 11
height:   0  1  0  2  1  0  1  3  2  1  2  1
maxLeft:  0  1  1  2  2  2  2  3  3  3  3  3
maxRight: 3  3  3  3  3  3  3  3  2  2  2  1
water:    0  0  1  0  1  2  1  0  0  1  0  0  → total = 6

Each maxLeft[i] builds on maxLeft[i-1] — a classic DP recurrence. The same logic applies to maxRight scanning from right to left.

Complexity:

Time: O(n) — three separate linear passes
Space: O(n) — two auxiliary arrays of size n

This is a strong interview answer. Most interviewers accept it. The two approaches below trade space for elegance.

Approach 3: Monotonic Stack — O(n) Time, O(n) Space

The stack-based approach processes bars left to right, maintaining a decreasing stack of indices. When the current bar is taller than the bar at the stack’s top, a “bowl” has formed — the current bar is the right boundary, the stack’s next element is the left boundary, and the popped element is the bottom.

public int trap(int[] height) {
    int n = height.length;
    int totalWater = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // Stores indices

    for (int current = 0; current < n; current++) {
        // While current bar is taller than the bar at stack top,
        // we have found the right boundary of a bowl
        while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
            int bottom = stack.pop();  // The bottom of the bowl

            if (stack.isEmpty()) break;  // No left boundary exists

            int leftBoundary = stack.peek();
            int rightBoundary = current;

            // Width of the water pool between boundaries
            int width = rightBoundary - leftBoundary - 1;

            // Height of water is bounded by the shorter boundary,
            // minus the bottom elevation
            int boundedHeight = Math.min(height[leftBoundary], height[rightBoundary])
                                - height[bottom];

            totalWater += width * boundedHeight;
        }

        stack.push(current);
    }

    return totalWater;
}

How the stack tracks bowls:

Walk through [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

Push index 0 (height 0). Stack: [0]
Index 1 (height 1) > height[0]. Pop 0. Stack empty → no left boundary. Push 1. Stack: [1]
Index 2 (height 0) ≤ height[1]. Push 2. Stack: [1, 2]
Index 3 (height 2) > height[2]. Pop 2 (bottom). Left boundary = index 1. Width = 3-1-1 = 1. Bounded height = min(1,2) - 0 = 1. Water += 1. Then height[3] > height[1]: pop 1 (bottom). Stack empty → no left boundary. Push 3. Stack: [3]
Continue this process through the rest of the array…

The stack approach computes water layer by layer horizontally, while the DP approach computes it column by column vertically. Both yield the same total.

When to use this approach: When the problem is a variation that requires tracking bounded regions (like “largest rectangle in histogram”), the monotonic stack transfers directly.

Complexity:

Time: O(n) — each index is pushed and popped at most once
Space: O(n) — stack holds at most n indices

Approach 4: Two Pointers — O(n) Time, O(1) Space (Optimal)

This is the approach that makes interviewers nod approvingly. It eliminates the auxiliary arrays from the DP approach by making a critical observation: you only need to process the side with the smaller maximum.

public int trap(int[] height) {
    int n = height.length;
    if (n <= 2) return 0;

    int left = 0;
    int right = n - 1;
    int maxLeft = 0;
    int maxRight = 0;
    int totalWater = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            // Left side is the bottleneck
            if (height[left] >= maxLeft) {
                maxLeft = height[left];  // Update left maximum
            } else {
                totalWater += maxLeft - height[left];  // Trap water
            }
            left++;
        } else {
            // Right side is the bottleneck
            if (height[right] >= maxRight) {
                maxRight = height[right];  // Update right maximum
            } else {
                totalWater += maxRight - height[right];  // Trap water
            }
            right--;
        }
    }

    return totalWater;
}

Why this works — the correctness argument:

The water at position i equals min(maxLeft[i], maxRight[i]) - height[i]. When height[left] <= height[right], you know that the right side has a bar at least as tall as height[right]. The true maxRight for position left is at least height[right], which is at least maxLeft (since height[left] <= height[right] and maxLeft >= height[left]).

The bottleneck is maxLeft. You do not need to know the exact maxRight — you only need to know that it is not the limiting factor. The symmetric argument applies when height[right] < height[left].

Dry run with [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

Step  left  right  maxL  maxR  action                water
1     0     11     0     0     h[0]=0 ≤ h[11]=1      +0 → 0
2     1     11     0     0     h[1]=1 ≤ h[11]=1      maxL=1
3     2     11     1     0     h[2]=0 ≤ h[11]=1      +1 → 1
4     3     11     1     0     h[3]=2 ≤ h[11]=1?     No → right side
                                h[11]=1, maxR=1       +0
5     3     10     1     1     h[3]=2 ≤ h[10]=2      maxL=2
6     4     10     2     1     h[4]=1 ≤ h[10]=2      +1 → 2
7     5     10     2     1     h[5]=0 ≤ h[10]=2      +2 → 4
8     6     10     2     1     h[6]=1 ≤ h[10]=2      +1 → 5
9     7     10     2     1     h[7]=3 ≤ h[10]=2?     No → right side
                                h[10]=2, maxR=2       +0
10    7     9      2     2     h[9]=1 < h[7]=3       +1 → 6
11    7     8      2     2     h[8]=2 < h[7]=3       +0
→ left = right = 7, loop ends. Total = 6 ✓

Complexity:

Time: O(n) — single pass with two pointers
Space: O(1) — four integer variables

Complexity Comparison

Approach	Time	Space	Pros	Cons
Brute Force	O(n²)	O(1)	Easy to understand and implement	Too slow for large inputs
Dynamic Programming	O(n)	O(n)	Clear, systematic, easy to debug	Uses two extra arrays
Monotonic Stack	O(n)	O(n)	Transfers to related problems	Harder to reason about correctness
Two Pointers	O(n)	O(1)	Optimal in both time and space	Correctness proof is non-obvious

Edge Cases

Handle these before writing your main logic:

Empty array or single element: No water can be trapped. Return 0.
Two elements: Water cannot be trapped between only two bars. Return 0.
All bars the same height: min(maxLeft, maxRight) - height[i] = 0 everywhere. Return 0.
Monotonically increasing: [1, 2, 3, 4, 5] — water runs off the left. Return 0.
Monotonically decreasing: [5, 4, 3, 2, 1] — water runs off the right. Return 0.
Single peak: [1, 2, 3, 2, 1] — no container formed. Return 0.
Two peaks with valley: [3, 0, 3] — water trapped = 3. The fundamental case.

Interviewer Tips

Which approach to present first: Start by explaining the key insight (water formula at each position), then describe the brute force approach in one sentence. Move directly to the DP solution — it demonstrates that you can optimize and is easy to code correctly. If the interviewer pushes for O(1) space, transition to two pointers.

Do not jump to two pointers immediately. Interviewers want to see your reasoning evolve. The leap from “I need maxLeft and maxRight” to “I only need to track the smaller side” is the signal of deep understanding.

Common follow-up questions:

Trapping Rain Water II (3D version): Given a 2D height map (matrix), compute trapped water. This requires a priority queue (min-heap) BFS approach, processing boundary cells inward from the lowest boundary.
Container With Most Water: A related but distinct problem — you want to maximize area between two bars, not sum trapped water across all bars. Two pointers apply, but the logic differs.
What if bars have different widths? The problem changes fundamentally. You need to integrate area rather than summing per-position water.

Time management: In a 45-minute interview, spend 5 minutes on problem understanding, 5 minutes on approach design, 15 minutes coding the DP or two-pointer solution, and 5 minutes on testing. Reserve the remaining time for follow-up discussion.