14.Trapping Rain Water

HardTwo Pointers · 5/5

Problem

Given n non-negative integers representing an elevation map where every bar has width 1, compute how many units of rain water are trapped between the bars after it rains.

Water sitting above bar i is held in place only if there is a taller-or-equal wall somewhere to its left and somewhere to its right.

Examples

Input:  height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: Water per index: [0,0,1,0,1,2,1,0,0,1,0,0] → total 6.

Input:  height = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: Water per index: [0,2,4,1,2,0] → total 9.

Constraints

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

💡 Key Insight

The water above index i is min(maxLeft[i], maxRight[i]) - height[i], where maxLeft[i] is the tallest bar at or left of i and maxRight[i] the tallest at or right of i. The water level is set by the lower of the two walls. Computing those maxima naively is O(n²); precomputing them is O(n) time and space; and two pointers get O(1) space by always processing the side whose wall is lower — because that side's limit is already known for sure.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Apply the formula directly: for every index, scan left for the tallest bar and scan right for the tallest bar, then add min(leftMax, rightMax) - height[i].

Algorithm

total = 0.
For each i:
- leftMax = max(height[0..i]), rightMax = max(height[i..n-1]).
- total += min(leftMax, rightMax) - height[i].
Return total.

Visualization

height = [4, 2, 0, 3, 2, 5]

i=2 (0): leftMax 4, rightMax 5 → min 4 − 0 = 4
i=3 (3): leftMax 4, rightMax 5 → min 4 − 3 = 1

Code

java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = 0; j <= i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            // Including height[i] in both maxima guarantees a non-negative result
            total += Math.min(leftMax, rightMax) - height[i];
        }
        return total;
    }
}

Complexity

Time: O(n²) — two linear scans per index.
Space: O(1).

Prefix and Suffix Max Arrays

TimeO(n)SpaceO(n)

Intuition

The brute force recomputes the same maxima repeatedly. Precompute them once: leftMax[i] = max(leftMax[i-1], height[i]) sweeping left-to-right, and rightMax[i] = max(rightMax[i+1], height[i]) sweeping right-to-left. Then each index's water is an O(1) lookup.

Algorithm

Fill leftMax from the left and rightMax from the right.
total = Σ min(leftMax[i], rightMax[i]) - height[i].

Visualization

i	0	1	2	3	4	5
height	4	2	0	3	2	5
leftMax	4	4	4	4	4	5
rightMax	5	5	5	5	5	5
water	0	2	4	1	2	0

Code

java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i]; // water level minus ground
        }
        return total;
    }
}

Complexity

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

Monotonic Stack

TimeO(n)SpaceO(n)

Intuition

Instead of computing water column by column, fill it layer by layer horizontally. Keep a stack of indices with decreasing heights. When a taller bar i arrives, the bar on top of the stack is a "floor" bounded by the new bar on the right and the next stack element on the left. The water over that floor is width × (min(leftWall, rightWall) - floor). Pop and repeat while the new bar is taller.

Algorithm

Empty stack of indices, total = 0.
For each i:
- While the stack is non-empty and height[i] > height[stack.peek()]:
  - floor = stack.pop(). If the stack is empty, break (no left wall).
  - left = stack.peek(), width = i - left - 1.
  - bounded = min(height[left], height[i]) - height[floor].
  - total += width * bounded.
- Push i.
Return total.

Visualization

height = [4, 2, 0, 3, 2, 5]

i=3 (3): pop floor 2 (0), left=1 (2): width 1 × (min(2,3) − 0) = 2
         pop floor 1 (2), left=0 (4): width 2 × (min(4,3) − 2) = 2
i=5 (5): pop floor 4 (2), left=3 (3): width 1 × (min(3,5) − 2) = 1
         pop floor 3 (3), left=0 (4): width 4 × (min(4,5) − 3) = 4
total = 2 + 2 + 1 + 4 = 9

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>(); // indices with decreasing heights
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int floor = stack.pop();
                if (stack.isEmpty()) {
                    break; // no wall on the left: water spills out
                }
                int left = stack.peek();
                int width = i - left - 1;
                int bounded = Math.min(height[left], height[i]) - height[floor];
                total += width * bounded; // one horizontal layer of water
            }
            stack.push(i);
        }
        return total;
    }
}

Complexity

Time: O(n) — each index is pushed and popped at most once.
Space: O(n) — the stack in the worst case (strictly decreasing heights).

Two PointersOptimal

TimeO(n)SpaceO(1)

Intuition

Keep leftMax (tallest bar seen from the left) and rightMax (tallest from the right) while moving left and right inward. If leftMax < rightMax, then for index left the true right-side maximum is at least rightMax, which is already larger than leftMax — so its water level is exactly leftMax, no matter what lies in between. We can settle left and move on. Symmetrically, settle right when rightMax <= leftMax. This replaces both arrays with two variables.

Algorithm

left = 0, right = n - 1, leftMax = height[0], rightMax = height[n-1], total = 0.
While left < right:
- If leftMax < rightMax: left++, leftMax = max(leftMax, height[left]), total += leftMax - height[left].
- Else: right--, rightMax = max(rightMax, height[right]), total += rightMax - height[right].
Return total.

Dry Run

flowchart TD
    A["height = [4,2,0,3,2,5]<br/>L=0, R=5, lMax 4, rMax 5"] -->|"4 lt 5: move L"| B["L=1 (2): lMax 4, add 2<br/>total 2"]
    B -->|"4 lt 5: move L"| C["L=2 (0): lMax 4, add 4<br/>total 6"]
    C -->|"4 lt 5: move L"| D["L=3 (3): lMax 4, add 1<br/>total 7"]
    D -->|"4 lt 5: move L"| E["L=4 (2): lMax 4, add 2<br/>total 9"]
    E -->|"4 lt 5: move L"| F["L=5 = R: stop"]
    F --> G["return 9"]

Code

java

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        int total = 0;
        while (left < right) {
            if (leftMax < rightMax) {
                // Right side has a wall taller than leftMax, so leftMax sets the level here
                left++;
                leftMax = Math.max(leftMax, height[left]);
                total += leftMax - height[left];
            } else {
                // Left side has a wall at least as tall as rightMax
                right--;
                rightMax = Math.max(rightMax, height[right]);
                total += rightMax - height[right];
            }
        }
        return total;
    }
}

Complexity

Time: O(n) — each index is settled exactly once as the pointers converge.
Space: O(1) — four integers.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Prefix and Suffix Max Arrays	O(n)	O(n)
Monotonic Stack	O(n)	O(n)
Two Pointers	O(n)	O(1)

Common Pitfalls

Using max(leftMax, rightMax) as the water level — water spills over the lower wall.
Excluding height[i] from its own leftMax/rightMax without guarding against negatives — a bar taller than both neighbours would add negative water.
In the stack approach, forgetting the stack.isEmpty() check after popping — the leftmost floor has no left wall and holds no water.
In the two-pointer approach, moving the pointer on the higher side — its level is not yet determined.