Trapping Rain Water

The interview narration

Say this out loud:

“For each column i in the interior, the water above it is min(leftMax, rightMax) − height[i], clamped at zero. Brute force: for every i, linear-scan the prefix and suffix to find those two maxes. $O(n^2)$ total, $O(1)$ space. Correct but slow — I’ll use it as a baseline.”

How it works, step by step

The outer loop ranges over interior columns ($i$ from $1$ to $n-2$); the first and last columns can never trap water because one of their sides has no bars to bound the water.

For each $i$:

1. Compute leftMax = max(H[0..i-1]) via std::max_element. Cost: $O(i)$.
2. Compute rightMax = max(H[i+1..n-1]) similarly. Cost: $O(n - i - 1)$.
3. Apply the formula: if min(leftMax, rightMax) > H[i], add the difference to the running total.
4. Otherwise the current bar is at least as tall as one of the bounds — no water.

The outer loop runs $n - 2$ times; each iteration does $O(n)$ work for the two max scans. Total: $O(n^2)$ time, $O(1)$ extra space.

The code

#include <algorithm>
#include <vector>

int trap(const std::vector<int>& height) {
    const int n = static_cast<int>(height.size());
    if (n < 3) return 0;
    int total = 0;
    for (int i = 1; i < n - 1; ++i) {
        const int leftMax = *std::max_element(height.begin(), height.begin() + i);
        const int rightMax = *std::max_element(height.begin() + i + 1, height.end());
        const int level = std::min(leftMax, rightMax);
        if (level > height[i]) total += level - height[i];
    }
    return total;
}

The std::max_element calls return iterators; dereferencing gives the actual max value. This is more idiomatic than hand-rolling two inner loops — interviewers notice.

Why it’s rejected

$n = 10^5$ gives $10^{10}$ operations, which is roughly a minute of wall time. Production code would never ship this, and no interviewer accepts it as the final answer. But it establishes the formula clearly, and every faster approach is a way to avoid recomputing the maxes.

What it gets right

• The formula is correct and direct. Every other approach builds on this same per-column sum; the brute force just computes it the slowest possible way.
• O(1) extra space. No auxiliary arrays or stacks. Until the next approach, this is the space-optimal baseline.
• Easy to verify on small inputs. If you’re ever unsure whether your optimized code is correct, run both on a 10-element input and compare.

The insight

The $O(n^2)$ in the brute force came from recomputing the same maxes over and over. Both leftMax[i] and rightMax[i] have overlapping structure — each one extends the previous:

That’s a one-line DP. Two linear passes give us the full arrays; a third pass sums the formula. Everything becomes $O(n)$ at the cost of two additional arrays of size $n$.

How it works, step by step

The figure below shows the two ceilings as dashed lines on top of the bars — green for leftMax, red for rightMax. The water at each column is the gap between the lower of the two dashed lines and the bar itself.

1. Forward pass for leftMax. Initialize leftMax[0] = height[0]. For $i$ from $1$ to $n-1$, leftMax[i] = max(leftMax[i-1], height[i]).
2. Backward pass for rightMax. Initialize rightMax[n-1] = height[n-1]. For $i$ from $n-2$ to $0$, rightMax[i] = max(rightMax[i+1], height[i]).
3. Summing pass. For each $i$, add min(leftMax[i], rightMax[i]) − height[i] to the total. (This is always ≥ 0 because min(leftMax[i], rightMax[i]) ≥ height[i] — both ceilings include height[i] in their maximum.)

The code

#include <algorithm>
#include <vector>

int trap(const std::vector<int>& height) {
    const int n = static_cast<int>(height.size());
    if (n < 3) return 0;

    std::vector<int> leftMax(n);
    std::vector<int> rightMax(n);

    leftMax[0] = height[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        rightMax[i] = std::max(rightMax[i + 1], height[i]);
    }

    int total = 0;
    for (int i = 0; i < n; ++i) {
        total += std::min(leftMax[i], rightMax[i]) - height[i];
    }
    return total;
}

Why this is a substantial improvement

The two prefix-max arrays are computed once, each in $O(n)$ time. The formula sum is another $O(n)$ pass. Total: $3n = O(n)$ time, $O(n)$ auxiliary space. From $n = 10^5$ being a minute of compute (brute) to milliseconds (prefix max).

The code also reads like the math — two DP recurrences followed by a sum. Interviewers can verify correctness at a glance, which matters when time is tight.

Why we can still do better

We pay $O(n)$ extra space for the two arrays. Every entry is read exactly once in the summing pass, then discarded. That’s wasteful — at any given column, the algorithm only needs one element from each array. If we can reconstruct those two values on the fly, we can reduce space to $O(1)$. That’s the two-pointer sweep.

Complexity

• Time: $O(n)$ — three linear passes.
• Space: $O(n)$ for leftMax and rightMax.

The insight

The three previous approaches think column-by-column. The stack approach thinks rectangle-by-rectangle. Every time a taller bar arrives to the right of some shorter bar, the shorter bar has just been enclosed between two taller ones (the left neighbor already on the stack and the new bar on the right). The area of the bounded rectangle is min(left, right) − bottom times the horizontal distance.

By processing bars left to right and maintaining a decreasing monotonic stack, every bar is pushed once and popped once. When a pop happens, we’re closing a rectangle — and summing those closed rectangles exactly equals the trapped water.

How it works, step by step

Maintain a stack of bar indices (not heights — we need the distance for the rectangle width) where heights strictly decrease from bottom to top. For each new bar height[i]:

1. While the stack is non-empty and height[i] > height[stack.top()]:
   • Pop the top index (call it bottom). This bar is about to be “closed” by a taller bar on its right.
   • If the stack is empty after the pop, no left bound exists — exit the inner loop.
   • Otherwise: peek the new top (call it left). The bar at left is the closest taller bar on bottom’s left.
   • Compute the rectangle: width = i − left − 1, heightBounded = min(height[i], height[left]) − height[bottom], and add width × heightBounded to the total.
2. Push i onto the stack.

At the end, any bars still on the stack are never “closed” (no taller bar arrives to their right), so they contribute nothing — which is correct, because water needs a taller bar on each side.

The code

#include <algorithm>
#include <stack>
#include <vector>

int trap(const std::vector<int>& height) {
    std::stack<int> stk;
    int total = 0;
    const int n = static_cast<int>(height.size());

    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && height[i] > height[stk.top()]) {
            const int bottom = stk.top();
            stk.pop();
            if (stk.empty()) break;
            const int left = stk.top();
            const int width = i - left - 1;
            const int bounded = std::min(height[i], height[left]) - height[bottom];
            total += width * bounded;
        }
        stk.push(i);
    }
    return total;
}

Amortized argument — why it’s $O(n)$

The outer for loop runs $n$ times. The inner while loop looks like it could blow up, but each iteration pops exactly one element from the stack. Across the full run, the total number of pops is bounded by the total number of pushes — which is $n$. So the total inner-loop work, summed over the whole algorithm, is $O(n)$.

This is the same amortized pattern as the chain-head filter in Longest Consecutive Sequence and the sliding-window maximum deque. A nested loop that looks $O(n^2)$ is actually $O(n)$ because each element is touched a bounded number of times.

When to use the stack approach

• When other histogram problems surround this one. Monotonic stacks solve Largest Rectangle in Histogram, Next Greater Element, Maximal Rectangle, and more. If your interview is walking through that family, the stack is a unifying tool.
• When you want to compute per-column rectangles and not just per-column water. The stack processes geometric regions; the two-pointer processes heights. Some follow-ups (e.g., “return the largest single puddle”) are easier from the stack view.
• When the two-pointer invariant feels shaky. Some candidates simply find the stack formulation easier to prove — one rectangle, one pop, visible correctness.

Complexity

• Time: $O(n)$ amortized. Each bar pushed once, popped at most once.
• Space: $O(n)$ for the stack. In the worst case (strictly decreasing heights), all $n$ bars are stacked.