Trapping Rain Water

1. Problem & Core Objective

The problem

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.

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

            █
    █ ~ ~ ~ █ █ ~ █
  █ █ ~ █ █ █ █ █ █ █
  0 1 0 2 1 0 1 3 2 1 2 1        ~ marks trapped water (6 units total)

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

What the interviewer is actually testing

This is the first Hard problem in the 150, and it's a genuine step up. It's testing whether you can:

1. Change the unit of analysis. The instinct is to think about puddles — irregular shapes spanning many bars. The unlock is to think column by column: how much water sits above this single position?
2. Derive the formula min(maxLeft, maxRight) − height[i], and justify the min.
3. Progressively optimize. O(n²) → O(n) with arrays → O(n) with O(1) space. The interviewer will walk you up this ladder.
4. State the two-pointer invariant. The O(1)-space version is not obvious, and "it works" is not an answer. The invariant is the question.

Don't jump straight to the optimal solution. Interviewers use this problem to watch you improve a solution. Starting with the prefix-array version and then folding it is a better performance than producing the two-pointer code from memory.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 2 × 10^4.

• O(n²) → 4 × 10^8. Borderline; probably too slow, and certainly not the intended answer.
• O(n) → trivial.

So O(n) is the target, and the follow-up will be O(1) space.

Step 2 — Change the unit of analysis

The hard way to think about this is "find each puddle and compute its volume". Puddles have irregular shapes, they merge, and finding their boundaries is fiddly.

The reframe:

Instead of asking "how big is each puddle?", ask "how much water sits directly above position i?" — then sum over all i.

Each column is independent. That turns a shape problem into n independent arithmetic problems.

Step 3 — Derive the per-column formula

How high does the water rise above position i?

Picture pouring water in. It rises until it would spill over an edge. It is held in by the tallest bar somewhere to the left, and the tallest bar somewhere to the right.

• If maxLeft is the tallest bar at or left of i, and maxRight the tallest at or right of i, then the water level at i is min(maxLeft, maxRight) — because water spills over the lower of the two walls.
• The bar at i itself occupies space from 0 up to height[i].

So:

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

And the total is Σ water[i].

Why min? If the left wall is 5 tall and the right is 3, water above 3 would flow out over the right side. The shorter wall determines the level.

Can this be negative? If height[i] is itself the tallest bar around, then min(maxLeft, maxRight) equals height[i] and the result is 0. It can never go below zero, because maxLeft and maxRight are defined to include position i — so both are at least height[i]. No clamping needed, and saying that shows you checked.

Step 4 — Compute the maxima efficiently

Naively, computing maxLeft[i] and maxRight[i] for each i means scanning outward each time: O(n²).

But these are running maxima — exactly what a prefix scan computes in one pass:

maxLeft[i]  = max(maxLeft[i-1],  height[i])      // one forward pass
maxRight[i] = max(maxRight[i+1], height[i])      // one backward pass

Two passes to build them, one pass to sum: O(n) time, O(n) space.

This is the same prefix/suffix decomposition as Product of Array Except Self — the answer at i depends on everything to the left and everything to the right, so precompute both directions.

Step 5 — Eliminate the arrays

Here's the step that makes it Hard.

The key realization: you don't always need to know both maxima. You only need the smaller of them — and sometimes you can know which one is smaller without computing the other.

Run two pointers from the ends, tracking leftMax and rightMax seen so far:

If height[l] < height[r], then there exists a bar of height at least height[r] somewhere to the right of l. So the true maxRight at position l is at least height[r], which is greater than height[l].

Meanwhile leftMax — the running max from the left — is what caps the water at l.

Since maxRight >= height[r] > height[l] and the water level is min(leftMax, maxRight), and leftMax >= height[l]... we need leftMax <= maxRight to conclude the min is leftMax.

Let's be careful and state the invariant precisely:

Invariant: when height[l] < height[r], we have leftMax <= rightMaxTrue at position l, where rightMaxTrue is the real maximum to the right of l.

Why: rightMaxTrue >= height[r] (since r is to the right of l). And leftMax at this moment is max(height[0..l]). We process positions in order, so whenever we're at l with height[l] < height[r], either leftMax <= height[r] <= rightMaxTrue — giving min = leftMax — or leftMax > height[r], which would mean the pointer would have moved the other way in earlier steps. The algorithm maintains that the side with the smaller bar is always the constrained one.

The practical statement to say in an interview:

"Whenever height[l] < height[r], the right side is guaranteed to hold up at least height[r], which exceeds height[l]. So the water at l is limited by the left side alone, and leftMax is all I need. I can settle position l without ever knowing the true maxRight. Symmetrically for the other branch."

Step 6 — A third framing: the monotonic stack

Rather than column by column, fill water in horizontal layers. A decreasing stack of bar indices; when a taller bar arrives, it forms the right wall of a puddle whose floor is the popped bar and whose left wall is the new stack top.

O(n) time, O(n) space. Worth knowing as the "I see the stack framing too" answer, and it's the bridge to Stack (§4).

3. Solution Paths

Approach 1 — Brute force: scan outward from each column

public int trap(int[] height) {
    int total = 0;
    for (int i = 0; i < height.length; i++) {
        int maxLeft = 0, maxRight = 0;
        for (int j = i; j >= 0; j--) maxLeft = Math.max(maxLeft, height[j]);
        for (int j = i; j < height.length; j++) maxRight = Math.max(maxRight, height[j]);
        total += Math.min(maxLeft, maxRight) - height[i];
    }
    return total;
}

Directly applies the formula, recomputing both maxima from scratch each time.

• Time: O(n²).
• Space: O(1).

Write this first if you're unsure. It's obviously correct and it makes the formula explicit, which is the thing the interviewer wants to see you derive.

Counter-questions on this approach

⭐ "That's O(n²). What exactly is being recomputed?"

maxLeft and maxRight are rescanned from scratch at every position, so the same prefix gets walked over and over. They're running maxima, which a single prefix pass computes once — that observation removes a whole factor of n.

"If it's quadratic, why write it at all?"

Because it makes the per-column formula explicit, and deriving that formula is the actual insight the question tests. Correctness is obvious here, which gives me a verified baseline to optimize against rather than guessing at the fast version directly.

Approach 2 — Prefix and suffix arrays

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

    int[] maxLeft = new int[n];
    int[] 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 total = 0;
    for (int i = 0; i < n; i++) total += Math.min(maxLeft[i], maxRight[i]) - height[i];
    return total;
}

Trace on height = [0,1,0,2,1,0,1,3,2,1,2,1]:

Total: 1 + 1 + 2 + 1 + 1 = 6 ✓

Read column 5: maxLeft = 2, maxRight = 3, so the level is 2; the bar is height 0; water = 2. Correct — that's the deepest point of the left puddle.

• Time: O(n) — three linear passes.
• Space: O(n) — two arrays.

This is the version to present as your first real solution. It makes the formula visible and is easy to verify.

Counter-questions on this approach

⭐ "You're using O(n) extra space. Can you drop it?"

Yes, and not by a mechanical trick. The key realization is that I never need both maxima — only the smaller of the two. And the comparison height[l] < height[r] tells me which side is the binding constraint without computing the other side at all. That's what collapses two arrays into two scalars.

"Why do the base cases sit outside the loops?"

maxLeft[0] has no predecessor and maxRight[n-1] has no successor, so neither can be computed by the recurrence. Note the backward loop also starts at n - 2, since n - 1 is already filled — that off-by-one is the usual bug here.

Approach 3 — Two pointers (optimal)

public int trap(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int total = 0;

    while (l < r) {
        if (height[l] < height[r]) {
            leftMax = Math.max(leftMax, height[l]);
            total += leftMax - height[l];
            l++;
        } else {
            rightMax = Math.max(rightMax, height[r]);
            total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

Trace on height = [0,1,0,2,1,0,1,3,2,1,2,1]:

Answer: 6 ✓

• Time: O(n) — one pointer moves per iteration.
• Space: O(1) — four integers.

The subtlety worth noting: leftMax is updated before the water is added, using height[l] itself. Since leftMax = max(leftMax, height[l]) >= height[l], the added amount leftMax - height[l] is never negative — no clamping required.

Counter-questions on this approach

⭐ "Why don't you need to know the true maxRight?"

Because of the branch condition. When height[l] < height[r], there is definitely a bar of height at least height[r] somewhere to the right of l — the one at r itself. So the true right-maximum at l is at least height[r], which strictly exceeds height[l]. That makes the left side the binding constraint, so min(leftMax, maxRight) resolves to leftMax and I can settle column l without ever computing the right side. The other branch is symmetric.

⭐ "Can the water you add ever be negative? Don't you need to clamp it?"

No clamping needed. leftMax is updated with height[l] before it's used, so leftMax >= height[l] always holds and leftMax - height[l] is never negative. If the bar at l is the tallest seen so far, the term is exactly zero.

"Could the running total overflow an int?"

The bound is roughly 2 × 10^4 columns times 10^5 maximum depth — about 2 × 10^9, uncomfortably close to Integer.MAX_VALUE at 2.1 × 10^9. The real maximum is far lower since you can't have every column at full depth, and the problem guarantees the answer fits. In production I'd use a long accumulator rather than rely on that.

Approach 4 — Monotonic stack

public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();   // indices, heights decreasing
    int total = 0;

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            int bottom = stack.pop();            // the floor of this puddle
            if (stack.isEmpty()) break;          // no left wall — water escapes

            int left = stack.peek();             // the left wall
            int width = i - left - 1;
            int depth = Math.min(height[left], height[i]) - height[bottom];
            total += width * depth;
        }
        stack.push(i);
    }
    return total;
}

How it works. Fills water in horizontal layers instead of vertical columns. Each pop identifies a puddle bounded by left (the new stack top) and i (the arriving bar), with bottom as its floor.

The stack.isEmpty() check handles a bar with nothing to its left — water would simply run off.

• Time: O(n) — each index is pushed once and popped at most once.
• Space: O(n) — worst case a strictly decreasing array pushes everything.

Worth presenting as a third framing, especially if the interviewer mentions stacks. It's not better than two pointers here, but it demonstrates range.

Counter-questions on this approach

⭐ "This is also O(n). Why isn't it your answer?"

Same time, but O(n) space versus O(1) — a decreasing input pushes every index onto the stack. It's a genuinely different framing: the stack fills water in horizontal layers while two pointers settles vertical columns. Worth knowing because the framing generalizes to Largest Rectangle in Histogram, but for this problem two pointers is strictly better on space and easier to explain.

"Why the stack.isEmpty() break immediately after popping?"

Because if nothing remains on the stack, the popped bar has no wall to its left and water would simply run off that side. Without the check you'd read a non-existent left wall.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force recomputes maxLeft and maxRight from scratch at every position — the same prefix scanned over and over. Precomputing them once removes an entire factor of n. Same "cache what you recompute" move as Product of Array Except Self.

Against the prefix/suffix arrays. Same O(n) time; the win is space. And the reason it works is genuinely interesting:

You never need both maxima — only the smaller one. And the comparison height[l] < height[r] tells you which side is the constraint, without computing the other side at all.

That's not a mechanical optimization; it's an observation about which information is actually load-bearing. Most O(n) → O(1) space reductions in this style come from noticing that a precomputed array is consumed in the same order it's produced, and can be replaced by a rolling variable. Here it's stronger — you're discovering that half the data is never needed.

Against the monotonic stack. Same time, worse space (O(n) vs O(1)), and harder to explain. It's a legitimate alternative framing rather than a competitor.

Why O(n) time is the floor. Every bar affects the answer; skipping one lets an adversary change the total. So O(n) is optimal, and O(1) space is optimal since four scalars suffice.

The relationship to Container With Most Water — they look similar and are not:

5. Java Prerequisites

Running maximum

leftMax = Math.max(leftMax, height[l]);

The one-line idiom for a prefix maximum. Initialize to 0 here because heights are non-negative; for possibly-negative values you'd use Integer.MIN_VALUE.

Building prefix/suffix arrays

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]);

Note the base cases are set outside the loop, and the backward loop starts at n - 2 (since n - 1 is already filled). Off-by-ones here are the usual bug.

Overflow analysis

total += leftMax - height[l];

Maximum water per column is 10^5, and there are at most 2 × 10^4 columns, so the total is bounded by 2 × 10^9 — which exceeds Integer.MAX_VALUE (≈ 2.1 × 10^9) only marginally.

In practice the true maximum is far lower (you can't have every column at max depth), and LeetCode guarantees the answer fits in an int. But this is exactly the kind of bound worth computing aloud: "Worst case is roughly 2 × 10⁹ which is uncomfortably close to int range — in production I'd use a long for the accumulator."

Deque as a stack

Deque<Integer> stack = new ArrayDeque<>();
stack.push(i); stack.pop(); stack.peek(); stack.isEmpty();

Use ArrayDeque, not java.util.Stack (a legacy synchronized Vector). See 02 §5.

Empty input

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

The two-pointer version handles it naturally (l = 0, r = -1, loop never runs). The prefix-array version would throw on maxLeft[0] = height[0], so it needs the guard. Constraints say n >= 1, but the guard costs nothing.

6. Interview Communication Guide

Clarifying questions

1. "Does each bar have width 1?" — yes; that's what makes the answer a simple sum of column heights.
2. "Can heights be zero?" — yes.
3. "Can the array be empty or have one element?" — with one bar, no water can be trapped.
4. "Is there a space requirement?" — if not stated, present the O(n) version then offer the O(1) refinement.
5. "Can I assume the total fits in an int?"

The pitch

"The hard way to think about this is puddle by puddle — irregular shapes that merge. Much easier: go column by column and ask how much water sits directly above each position.

For position i, water rises until it spills over an edge. It's held in by the tallest bar to the left and the tallest to the right — and it spills over the lower of those two. So the level is min(maxLeft, maxRight), and the water is that minus height[i]. Total is the sum over all i.

Computing those maxima naively is O(n²). But they're just running maxima, so one forward pass and one backward pass give me both arrays — O(n) time, O(n) space.

I can then drop the arrays. Notice I only ever need the smaller of the two maxima. If height[l] < height[r], then there's definitely a bar at least height[r] somewhere to the right, which is taller than height[l] — so the left side is the binding constraint and leftMax alone determines the water at l. I can settle that column without ever knowing the true right maximum. Symmetrically for the other side.

That gives O(n) time and O(1) space. There's also a monotonic-stack version that fills water in horizontal layers — same time, but O(n) space."

Edge cases to raise proactively

[1,2,3,4] is the one to volunteer — a monotonic array traps nothing, and it's a good sanity check that your formula doesn't produce negatives. Explain why: at every position, min(maxLeft, maxRight) equals height[i] itself, so each term is exactly 0.

[5,0,5] is the clearest demonstration of the formula: at index 1, maxLeft = 5, maxRight = 5, min = 5, bar height 0 → 5 units.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "Trapping Rain Water II — a 2-D grid."

Fundamentally harder. Water escapes in any direction, not just left/right, so there's no simple prefix/suffix decomposition. The approach is a min-heap starting from the entire border: repeatedly pop the lowest boundary cell, and for each unvisited neighbour, the water level there is max(currentLevel, neighbourHeight). It's Dijkstra-like — you always expand from the lowest current boundary. O(mn log(mn)). See 14 — Heaps.

"What if you could remove k bars to maximize trapped water?"

Much harder — the greedy/two-pointer structure breaks, because removing a bar changes the maxima globally. You'd be looking at DP over (position, bars removed) state, and it's not a standard interview problem. Worth saying that you recognize the structure breaks rather than guessing.

"What if the bars had varying widths?"

The formula becomes width[i] × (min(maxLeft, maxRight) − height[i]). The algorithm is unchanged; only the accumulation term differs.