Trapping Rain Water

HardTwo Pointers · Prefix Max🧩 Two Pointers LeetCode #42 ↗Updated Oct 30, 2026

Problem

height describes an elevation map of unit-width bars. After it rains, water settles in the dips between bars. Compute the total units of water held above all bars.

Input[0,1,0,2,1,0,1,3,2,1,2,1]Output6

Input[4,2,0,3,2,5]Output9

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

Try it yourself

Java

class Solution {
    public int trap(int[] height) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Water above bar i is min(maxLeft(i), maxRight(i)) - height[i]. You only need the smaller of the two maxima — so whichever side has the lower max can be settled immediately.

PatternTwo Pointers

Instinct Sorted input, a pair/triple hitting a target, or something symmetric? Put one pointer at each end and move the one that can only improve things.

Memory hack Squeeze from both ends - every step throws away a whole row of the brute-force grid.

Open the Two Pointers guide →

Approaches

Brute ForceScan Left & Right for Every Bar

Time O(n²)Space O(1)

For each bar, scan to find the tallest bar on its left and on its right (both including itself). The water level there is the lower of the two; subtract the bar's own height. Including the bar makes the result never negative.

Java

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

Directly encodes the formula, but rescans the array for every bar.

BetterPrefix / Suffix Max Arrays

Time O(n)Space O(n)

The brute force recomputes the same maxima. Precompute leftMax[i] (left-to-right running max) and rightMax[i] (right-to-left), then one more pass applies the formula.

Java

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;
}

Linear time, but two extra arrays of size n.

OptimalTwo Pointers with Running Maxima

Time O(n)Space O(1)

Walk left and right inward. If height[left] < height[right], some bar on the right is at least height[left], so the left side's level is bounded by leftMax alone — settle left and advance. Symmetric for the right.

Java

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) { // left side is the bottleneck
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Dry run[4,2,0,3,2,5]

l leftr right changed

1
4
l
2

0

3

2

5
r
4<5: lMax=4, +0
2
4

2
l
0

3

2

5
r
2<5: +4-2=2 (w=2)
3
4

2

0
l
3

2

5
r
0<5: +4 (w=6)
4
4

2

0

3
l
2

5
r
3<5: +1 (w=7)
5
4

2

0

3

2
l
5
r
2<5: +2 (w=9)
6
4

2

0

3

2

5
l r
l == r → 9 ✔

Single pass, constant space — the interview favourite.

Pro tip

A monotonic decreasing stack also solves it in O(n), filling water layer by layer — a good follow-up to mention.

At a glance

Level	Approach	Time	Space
Brute Force	Scan Left & Right for Every Bar	`O(n²)`	`O(1)`
Better	Prefix / Suffix Max Arrays	`O(n)`	`O(n)`
Optimal	Two Pointers with Running Maxima	`O(n)`	`O(1)`

Common pitfalls

Using max of the two sides instead of min for the level.
Comparing leftMax/rightMax wrongly — must move the lower side.
Adding negative water: update the max before subtracting the bar height.

Interview tips

Write the per-bar formula first; every approach is just a faster way to evaluate it.
Justify the two-pointer move: the opposite side is guaranteed to be at least as tall.
Contrast with Container With Most Water (inner bars ignored there).

Pattern

Prefix/suffix max → two pointers → per-index answers that depend on the max to each side.

My notes saved in this browser