Trapping Rain Water

Problem. Given heights $h_0,\dots ,h_{n-1}$ representing an elevation map, compute how much water is trapped after rain.

The key observation

Water above position $i$ is bounded by the tallest bar to its left and to its right:

${\text{water}}_i=\max (0,\min ({\max }_{j\le i}{h}_j,{\max }_{j\ge i}{h}_j)-h_i).$

Two pointers — $O(n)$ time, $O(1)$ space

Move the pointer on the shorter side; that side’s maximum is then the binding constraint.

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

Why moving the shorter side is safe: if h[l] < h[r], then whatever lies between them, the right side has some bar at least as tall as h[l]. So the water at $l$ is determined entirely by leftMax — no need to know the true right maximum.

The prefix/suffix version — $O(n)$ space, easier to see

vector<int> preMax(n), sufMax(n);
partial_sum(h.begin(), h.end(), preMax.begin(), [](int a, int b){ return max(a,b); });
// same from the right for sufMax
for (int i = 0; i < n; i++) total += min(preMax[i], sufMax[i]) - h[i];

Write this first if you are unsure; convert to two pointers only if the space matters.

Monotonic stack — layer by layer

long long trapStack(const vector<int>& h) {
    stack<int> st;
    long long total = 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;
            int width = i - st.top() - 1;
            int height = min(h[st.top()], h[i]) - h[bottom];
            total += (long long)width * height;
        }
        st.push(i);
    }
    return total;
}

Fills water in horizontal layers rather than vertical columns. Same answer, different decomposition — and the monotonic stack structure generalises to related problems.

The three approaches compared

Method	Time	Space	Note
Brute force (max on each side per $i$)	$O(n^2)$	$O(1)$	the starting point
Prefix/suffix maxima	$O(n)$	$O(n)$	clearest
Two pointers	$O(n)$	$O(1)$	optimal
Monotonic stack	$O(n)$	$O(n)$	layer decomposition

Variants

Variant	Method
2D trapping rain water	priority queue from the border inward (a Dijkstra-like flood)
Container with most water	two pointers on $\min (h_l,h_r)\times (r-l)$
Largest rectangle in a histogram	monotonic stack
Water with a leak / drainage	modify the boundary condition
Maximum water after removing $k$ bars	harder; DP or greedy depending on the constraints

The 2D version

Water on a grid escapes over the lowest point of the boundary. Push all border cells into a min-heap; repeatedly pop the lowest cell, and for each unvisited neighbour, trap $\max (0,\text{level}-h)$ water and push it with height $\max (\text{level},h)$.

priority_queue<tuple<int,int,int>, vector<...>, greater<>> pq;   // (height, r, c)
// push all border cells, then flood inward
while (!pq.empty()) {
    auto [ht, r, c] = pq.top(); pq.pop();
    for (each neighbour (nr,nc) not visited) {
        total += max(0, ht - g[nr][nc]);
        pq.push({max(ht, g[nr][nc]), nr, nc});
        visited[nr][nc] = true;
    }
}

$O(nm\log (nm))$. This is a genuinely nice application of a priority queue — the “water level” propagates inward exactly as Dijkstra’s distances do.

Why it is worth knowing

It is the clearest example of the two-pointer domination argument: you may advance the pointer whose side is provably not the binding constraint. The same reasoning appears in “container with most water”, the two-sum on a sorted array, and merge-based algorithms.

See also: Two Pointers · Monotonic Stack · Largest Rectangle