Trapping Rain Water [Hard] — Build the Intuition From Scratch (LeetCode 42)

Problem Statement

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

Example 1:

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

Example 2:

Input:  height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 20,000
• 0 <= height[i] <= 100,000

Visual — Elevation Map for [0,1,0,2,1,0,1,3,2,1,2,1]:

                 _
        _       | |_    _
   _   | |_   _| | |_  | |_
  | |__| | |_| |      |_|   |
  0  1  0  2  1  0  1  3  2  1  2  1
  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^
  0  1  2  3  4  5  6  7  8  9 10 11

Water trapped (shown as ~):
  0  0  1  0  1  2  1  0  0  1  0  0  = 6 units total

• Why This Problem Matters
• Building The Intuition From Scratch
• How much water sits on top of position i?
• Walking through the example position by position
• Three Approaches — Building Up
• Approach 1: Brute Force — O(n²) Time, O(1) Space
• Approach 2: Prefix/Suffix Arrays — O(n) Time, O(n) Space
• Approach 3: Two Pointers — O(n) Time, O(1) Space
• Why The Two-Pointer Works — The Invariant
• The key question an interviewer will ask
• The invariant
• Why moving the wrong pointer would break it
• Visual Dry Run — Two Pointers on [0,1,0,2,1,0,1,3,2,1,2,1]
• Common Mistakes
• Solutions
• Python — All 3 Approaches
• JavaScript — All 3 Approaches
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

Trapping Rain Water (LeetCode 42) is one of the most respected Hard problems in technical interviews — and it earns that status for a precise reason. It is not hard because the brute-force solution is complex. It is hard because there are three progressively clever solutions, and each one requires you to see the problem differently. Amazon uses it to test whether you can reduce a 2D visual problem to a 1D mathematical one. Google uses it to see if you can articulate why the space-optimized solution is correct — not just write it from memory. Meta and Microsoft use follow-up variants like the 3D version (LeetCode 407) to continue pushing after a correct solution. The candidates who fail this problem in a loop are usually those who memorized the two-pointer code but cannot answer a single question about its correctness. This guide will make sure you can.

Building The Intuition From Scratch

How much water sits on top of position i?

Start with a single question: for a bar at index i, how high does the water reach above it?

Think of a swimming pool cross-section. Water at position i is trapped between the tallest wall to its left and the tallest wall to its right. The water level rises to the height of the shorter of those two walls — because if it went any higher, it would spill over the shorter side.

So the water contribution at index i is:

water[i] = min(left_max[i], right_max[i]) - height[i]

If this value is negative (the bar is taller than one of the walls), no water is trapped there — we treat it as 0.

Walking through the example position by position

For height = [0,1,0,2,1,0,1,3,2,1,2,1]:

Index | height | left_max | right_max | min(L,R) | water
  0   |   0    |    0     |     3     |    0     |   0
  1   |   1    |    1     |     3     |    1     |   0
  2   |   0    |    1     |     3     |    1     |   1  <-- 1 unit trapped
  3   |   2    |    2     |     3     |    2     |   0
  4   |   1    |    2     |     3     |    2     |   1  <-- 1 unit trapped
  5   |   0    |    2     |     3     |    2     |   2  <-- 2 units trapped
  6   |   1    |    2     |     3     |    2     |   1  <-- 1 unit trapped
  7   |   3    |    3     |     3     |    3     |   0
  8   |   2    |    3     |     2     |    2     |   0
  9   |   1    |    3     |     2     |    2     |   1  <-- 1 unit trapped
 10   |   2    |    3     |     2     |    2     |   0
 11   |   1    |    3     |     1     |    1     |   0
                                          Total  =   6

This table is the heart of the problem. Every approach is just a different way to compute left_max and right_max efficiently.

Three Approaches — Building Up

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

The most direct translation of our formula: for each position i, scan all the way left to find left_max, then scan all the way right to find right_max.

for each index i:
    left_max  = max(height[0..i])
    right_max = max(height[i..n-1])
    water    += max(0, min(left_max, right_max) - height[i])

This is correct but wasteful — we recompute the same maximums over and over. For a 20,000-element array, that is 400 million comparisons.

Where candidates go wrong here: Forgetting the max(0, ...) guard and returning negative water for positions at the peaks.

Approach 2: Prefix/Suffix Arrays — O(n) Time, O(n) Space

The observation: the brute force rescans are redundant. We can precompute all the left maximums in one left-to-right pass, and all the right maximums in one right-to-left pass, then combine them in a third pass.

# Pass 1: build left_max array
left_max[0] = height[0]
for i in range(1, n):
    left_max[i] = max(left_max[i-1], height[i])

# Pass 2: build right_max array
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
    right_max[i] = max(right_max[i+1], height[i])

# Pass 3: compute water
total = 0
for i in range(n):
    total += max(0, min(left_max[i], right_max[i]) - height[i])

This reduces time to O(n) at the cost of O(n) extra space. Clean, easy to reason about, easy to test. This is the approach most interviewers are happy to accept as a first solution before pushing you to optimize space.

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

This is the optimal solution. It eliminates the two extra arrays by using a clever observation about what information we actually need.

left, right = 0, n - 1
left_max = right_max = 0
total = 0

while left < right:
    if height[left] < height[right]:
        if height[left] >= left_max:
            left_max = height[left]
        else:
            total += left_max - height[left]
        left += 1
    else:
        if height[right] >= right_max:
            right_max = height[right]
        else:
            total += right_max - height[right]
        right -= 1

The code is short. But candidates who cannot explain why we pick the smaller side will be found out immediately by an experienced interviewer. The next section is dedicated entirely to this.

Why The Two-Pointer Works — The Invariant

This is the section that separates people who understand the algorithm from those who memorized it.

The key question an interviewer will ask

After you write the two-pointer code, an interviewer at Google or Amazon will say: "Why do we process the left pointer when height[left] < height[right]? Why not the right pointer?"

The invariant

Here is the insight, stated precisely:

Whichever side has the smaller current maximum, we already have enough information to compute the exact water at that pointer — right now. We do not need to know what is on the other side.

Let's unpack this. Suppose at some moment left_max = 2 and right_max = 5. We are at left pointer.

• We know the tallest bar seen so far from the left side is 2.
• We know there is a bar of height 5 somewhere to the right (because right_max = 5).
• Therefore, the true right_max for position left is at least 5.
• The water at position left is min(left_max, true_right_max) - height[left].
• Since left_max = 2 < 5 <= true_right_max, the min is always left_max = 2.
• So water at left = left_max - height[left], regardless of what the true right maximum turns out to be.

We can compute this safely right now. We advance the left pointer.

The moment we would process the right side: When right_max <= left_max. By symmetric reasoning, we know the true left maximum is at least left_max, which is at least right_max, so the bottleneck is right_max and we can compute water at right safely.

Why moving the wrong pointer would break it

If we always advanced the left pointer (ignoring which side has the smaller max), we might encounter a situation where we compute water using left_max as the cap — but the actual right maximum is smaller than left_max, meaning the real water level is lower. We would overcount. The invariant ensures we only compute water when the side we are processing is definitively the bottleneck.

This is exactly the kind of correctness argument — not just pattern recognition — that distinguishes a senior engineer's explanation from a candidate who crammed LeetCode the night before.

Visual Dry Run — Two Pointers on [0,1,0,2,1,0,1,3,2,1,2,1]

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
indices   0  1  2  3  4  5  6  7  8  9 10 11

Step | left | right | lmax | rmax | action                          | water
  1  |   0  |  11   |   0  |   0  | h[0]=0 < h[11]=1 → process left | 0+0=0
  2  |   1  |  11   |   0  |   1  | h[1]=1 ≥ h[11]=1 → process right| rmax=1
  3  |   1  |  10   |   0  |   1  | h[1]=1 = h[10]=2 → process right| rmax=2
  4  |   1  |   9   |   0  |   2  | h[1]=1 < h[9]=1  → process left | lmax=1
  5  |   2  |   9   |   1  |   2  | h[2]=0 < h[9]=1  → process left | 0+1-0=1
  6  |   3  |   9   |   1  |   2  | h[3]=2 > h[9]=1  → process right| 0+2-1=1
  7  |   3  |   8   |   1  |   2  | h[3]=2 = h[8]=2  → process right| rmax=2
  8  |   3  |   7   |   1  |   2  | h[3]=2 < h[7]=3  → process left | lmax=2
  9  |   4  |   7   |   2  |   2  | h[4]=1 < h[7]=3  → process left | 0+2-1=1
 10  |   5  |   7   |   2  |   2  | h[5]=0 < h[7]=3  → process left | 0+2-0=2
 11  |   6  |   7   |   2  |   2  | h[6]=1 < h[7]=3  → process left | 0+2-1=1
 12  |   7  |   7   |   2  |   2  | left == right → STOP

Total water = 0 + 1 + 1 + 2 + 1 = 6  ✓

The pointers never cross and each index is visited exactly once — O(n) total work.

Common Mistakes

1. Off-by-one on initialization. Initializing left_max or right_max to 0 is correct here because heights are non-negative. If the problem allowed negative heights, you would need left_max = height[0] and right_max = height[n-1]. Know why 0 works for this specific problem.

2. Forgetting the max(0, ...) guard in the brute force. If height[i] exceeds both neighbors (a peak), the formula gives a negative number. Water cannot be negative — always clamp at zero.

3. Advancing the wrong pointer in two pointers. The invariant requires processing the side with the smaller maximum, not the smaller current height. Moving based on current height instead of running max is a subtle but fatal bug.

4. Confusing two different problems. "Container With Most Water" (LeetCode 11) also uses two pointers on a height array, but the logic is completely different. In that problem you move the pointer at the shorter current bar. In Trapping Rain Water you move the pointer at the smaller running maximum. Mixing these up under interview pressure is extremely common.

5. Not handling edge cases. Arrays of length 0, 1, or 2 can never trap water. Many candidates' two-pointer solutions silently return 0 for these, which happens to be correct — but you should state this explicitly rather than letting the interviewer wonder.

Solutions

Python — All 3 Approaches

from typing import List

# ─── Approach 1: Brute Force — O(n²) time, O(1) space ───────────────────────
class SolutionBrute:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        total = 0
        for i in range(n):
            # Scan left to find tallest bar on the left (inclusive)
            left_max = max(height[:i+1])
            # Scan right to find tallest bar on the right (inclusive)
            right_max = max(height[i:])
            # Water is capped by the shorter wall; can't be negative
            total += max(0, min(left_max, right_max) - height[i])
        return total


# ─── Approach 2: Prefix/Suffix Arrays — O(n) time, O(n) space ───────────────
class SolutionPrefixSuffix:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        # Precompute the tallest bar from the left up to each index
        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])

        # Precompute the tallest bar from the right down to each index
        right_max = [0] * n
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        # Water at each position = min(walls) - floor
        total = 0
        for i in range(n):
            total += max(0, min(left_max[i], right_max[i]) - height[i])
        return total


# ─── Approach 3: Two Pointers — O(n) time, O(1) space ───────────────────────
class SolutionTwoPointers:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        total = 0

        while left < right:
            if height[left] < height[right]:
                # Right side has a taller (or equal) bar — left_max is the cap
                if height[left] >= left_max:
                    left_max = height[left]   # Update running left max
                else:
                    total += left_max - height[left]  # Trapped water
                left += 1
            else:
                # Left side has a taller (or equal) bar — right_max is the cap
                if height[right] >= right_max:
                    right_max = height[right]  # Update running right max
                else:
                    total += right_max - height[right]  # Trapped water
                right -= 1

        return total

JavaScript — All 3 Approaches

// ─── Approach 1: Brute Force — O(n²) time, O(1) space ────────────────────
var trapBrute = function(height) {
    const n = height.length;
    let total = 0;

    for (let i = 0; i < n; i++) {
        // Find the tallest bar to the left of i (inclusive)
        let leftMax = 0;
        for (let l = 0; l <= i; l++) leftMax = Math.max(leftMax, height[l]);

        // Find the tallest bar to the right of i (inclusive)
        let rightMax = 0;
        for (let r = i; r < n; r++) rightMax = Math.max(rightMax, height[r]);

        // Water is always non-negative
        total += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
    }
    return total;
};


// ─── Approach 2: Prefix/Suffix Arrays — O(n) time, O(n) space ────────────
var trapPrefixSuffix = function(height) {
    const n = height.length;
    if (n === 0) return 0;

    // Build left-max prefix array
    const leftMax = new Array(n);
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    // Build right-max suffix array
    const rightMax = new Array(n);
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    // Sum up trapped water at each position
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
    }
    return total;
};


// ─── Approach 3: Two Pointers — O(n) time, O(1) space ────────────────────
var trap = function(height) {
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let total = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            // The right side is taller — process the left pointer
            if (height[left] >= leftMax) {
                leftMax = height[left];      // New left boundary found
            } else {
                total += leftMax - height[left];  // Water fills this valley
            }
            left++;
        } else {
            // The left side is taller (or equal) — process the right pointer
            if (height[right] >= rightMax) {
                rightMax = height[right];    // New right boundary found
            } else {
                total += rightMax - height[right];  // Water fills this valley
            }
            right--;
        }
    }
    return total;
};

Complexity Analysis

In practice, both O(n) solutions run at similar speed on LeetCode because cache behavior favors the prefix/suffix approach (sequential memory access). The two-pointer approach wins on memory — important for embedded systems or when called millions of times per second in a stream processing context.

Follow-up Questions

Interviewers at senior levels will push the problem further. Here are the four most common follow-ups with approach hints:

1. What if bars have different widths? The formula generalizes: water[i] = width[i] * max(0, min(left_max, right_max) - height[i]). Each bar multiplies its unit water contribution by its width. The two-pointer structure stays the same.

2. Trapping Rain Water II — 3D version (LeetCode 407) Given an m x n height matrix, compute total 3D water volume. The two-pointer trick does not extend to 2D. Instead, use a min-heap (priority queue). Add all boundary cells to the heap. Pop the minimum, check its four neighbors — if a neighbor is shorter, water fills the gap. Push neighbors into the heap with height max(neighbor_height, current_height). This is a BFS/Dijkstra hybrid, O(mn log(mn)).

3. Largest Rectangle in Histogram (LeetCode 84) This problem shares the "look left and right from each bar" structure but inverts the logic — instead of finding the minimum of two walls, you find the widest rectangle under a given height. The classic O(n) approach uses a monotonic stack: maintain bars in increasing order; when a shorter bar arrives, pop and compute rectangles. Understanding rain water makes this problem considerably more approachable.

4. Count water as a stream (online version) If bars arrive one at a time from the left and you must report total water so far after each bar, the two-pointer approach does not apply (no right side yet). A monotonic stack that computes water on each "downslope" event is the right tool. This tests whether you understand that two pointers require knowing the full array.

This Pattern Solves

The "look left and right for a boundary" pattern appears in several adjacent problems:

The unifying thread: whenever you need to efficiently answer "what is the nearest/maximum/minimum element to my left or right?" — think prefix arrays, suffix arrays, monotonic stacks, or two pointers.

Key Takeaway

The formula water[i] = min(left_max, right_max) - height[i] is the entire problem — every solution is just a different strategy for computing those two maximums efficiently. The prefix array approach makes this obvious. The two-pointer approach is an optimization that exploits the fact that you only need the smaller of the two maximums to compute water safely, which means you can process the smaller side immediately without knowing the other side's true maximum. If you can explain that invariant clearly under pressure, you have demonstrated exactly what senior engineers at Amazon and Google are looking for: the ability to reason about correctness, not just produce working code.