Trapping Rain Water

Problem

Given an array of non-negative integers representing wall heights of width 1, compute how much rain water the terrain can trap between walls.

Constraints

• 0 ≤ heights.length ≤ 2·10⁴
• 0 ≤ heights[i] ≤ 10⁵

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def trap(self, heights):
        l, r = 0, len(heights) - 1
        lm = rm = total = 0
        while l < r:
            if heights[l] < heights[r]:
                lm = max(lm, heights[l])
                total += lm - heights[l]
                l += 1
            else:
                rm = max(rm, heights[r])
                total += rm - heights[r]
                r -= 1
        return total

Java

import java.util.*;

class Solution {
    public int trap(int[] heights) {
        // Monotonic (decreasing) stack of indices. When a taller bar
        // arrives, each bar we pop is a basin bottom — the water above
        // it is bounded by the shorter of the new bar and the bar still
        // below it on the stack.
        Deque<Integer> stack = new ArrayDeque<>();
        int water = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] > heights[stack.peek()]) {
                int bottom = stack.pop();
                if (stack.isEmpty()) break;
                int width = i - stack.peek() - 1;
                int depth = Math.min(heights[i], heights[stack.peek()])
                            - heights[bottom];
                water += width * depth;
            }
            stack.push(i);
        }
        return water;

        // Alternatives: prefix/suffix max arrays (the Prefix / Sweep
        // view), or two converging pointers with leftMax / rightMax
        // for O(1) extra space.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.