Trapping Rain Water

hardTwo Pointers59 stepsJava · Python · C++

Water above a bar is min(maxLeft, maxRight) - height. With two pointers, the side with the lower bar is limited by its own running max, because the other side is known to have something at least as tall. So process that side, add its water, and move inward.

▶ Watch the animated trace

Traced input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → 6. Original problem: neetcode.io/problems/trapping-rain-water

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

One pass with four variables, instead of two O(n) max arrays.

Key idea

Water at i is min(leftMax, rightMax) - h[i].
If h[l] < h[r], the right side has a bar ≥ h[l], so the water at l depends only on leftMax.
Update the running max first; if the current bar is the new max, it holds 0 water.
Move the pointer on the lower side and repeat until they meet.

Common mistakes

Using the global max instead of the running max on each side.
Computing max arrays is fine (O(n) space) but know the O(1) version.
Moving the taller side gives wrong answers.

Solution

Java

int trap(int[] height) {
    int l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, total = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            leftMax = Math.max(leftMax, height[l]);
            total += leftMax - height[l];
            l++;
        } else {
            rightMax = Math.max(rightMax, height[r]);
            total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

Python

def trap(height: List[int]) -> int:
    l, r = 0, len(height) - 1
    left_max = right_max = total = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            total += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            total += right_max - height[r]
            r -= 1
    return total

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No bars The loop never runs.	`height = []`	`0`
Increasing heights Nothing on the left can hold water.	`height = [1, 2, 3, 4]`	`0`
V shape The middle holds min(3, 3) - 0 = 3.	`height = [3, 0, 3]`	`3`
Uneven walls The shorter wall (4) caps the water.	`height = [4, 2, 0, 3, 2, 5]`	`9`
Two bars No space between them.	`height = [5, 5]`	`0`