Problem 6.7 · Two PointersHard

Trapping Rain Water

PatternTwo Pointers: Opposite Ends Prefix Sum Monotonic Stack

What it teaches: Water above a bar is min(tallest on the left, tallest on the right) − its height. Prefix/suffix maxima give O(n); two pointers do it in O(1) space.

Practise it on judges as “Trapping Rain Water”.

The problem

height[i] is the height of a bar of width 1. Compute how much rain water is trapped between the bars after it rains.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵

Pattern clues in the wording

→ Each position depends on the maximum to its left and to its right
→ Prefix/suffix summary → then reduce space with two pointers

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int trap(int[] height) {
        int water = 0;
        return water;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	height = [0,1,0,2,1,0,1,3,2,1,2,1]	6
2	height = [4,2,0,3,2,5]	9

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Brute force: scan both sides for every bar · O(n²)2. Better: prefix and suffix maxima · O(n)3. Optimal: two pointers with running maxima · O(n)

Brute force: scan both sides for every bar

Time O(n²) Space O(1)

For each bar, find the tallest bar to its left and to its right, then add min(left, right) − height.

Approach 1

class Solution {
    public int trap(int[] height) {
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            int left = 0, right = 0;
            for (int j = 0; j <= i; j++) left = Math.max(left, height[j]);
            for (int j = i; j < height.length; j++) right = Math.max(right, height[j]);
            water += Math.min(left, right) - height[i];
        }
        return water;
    }
}

Verdict: 4 × 10⁸ steps at the limit: too slow. Repeated work: re-finding the same maxima.

Better: prefix and suffix maxima

Time O(n) Space O(n)

Precompute leftMax[i] (tallest in 0..i) and rightMax[i] (tallest in i..n−1) in two passes, then sum min(leftMax, rightMax) − height in a third.

Approach 2

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n], 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 water = 0;
        for (int i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
        return water;
    }
}

Verdict: Linear time; the next approach removes the arrays.

Optimal: two pointers with running maxima

Time O(n) Space O(1)

Keep leftMax and rightMax seen so far from each end. If leftMax < rightMax, the water at L is decided by leftMax (there's a taller bar somewhere on the right), so add leftMax − height[L] and move L. Otherwise do the same on the right.

▶ Dry run: The smaller side is already decidedheight = [4, 2, 0, 3, 2, 5]

↑L

↑R

State(vars)

leftMax = 4rightMax = 5water = 0

Step 1/5leftMax 4 < rightMax 5: the left side is decided. Bar 0 holds 4 − 4 = 0. Move L.

Approach 3

class Solution {
    public int trap(int[] height) {
        int L = 0, R = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (L < R) {
            leftMax = Math.max(leftMax, height[L]);
            rightMax = Math.max(rightMax, height[R]);
            if (leftMax < rightMax) {
                water += leftMax - height[L];
                L++;
            } else {
                water += rightMax - height[R];
                R--;
            }
        }
        return water;
    }
}

Verdict: One pass, two pointers, two variables.

Before you submit

Edge cases and common mistakes

Test these inputs

Fewer than 3 bars → 0
Strictly increasing or decreasing → 0
Flat bars
A deep valley in the middle

Mistakes people make

Using max(leftMax, rightMax) instead of min.
Moving the pointer on the taller side.

Interview

Follow-up questions

How does the monotonic stack solution work?

What about a 2D height map?

Command Palette