roadmap/two-pointers/Trapping Rain Water

Trapping Rain Water

HardAmazonGoogleMetaAppleBloomberg

Problem

Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

Intuition — the key insight

Water above position i = min(maxLeft[i], maxRight[i]) - height[i]. With two pointers: if maxLeft < maxRight, the water at left pointer is determined by maxLeft alone — process it and move left inward. Otherwise process right.

Approach

Two pointer O(1) space

lo=0, hi=n-1, maxL=0, maxR=0. While lo<hi: if maxL<=maxR, water[lo]=maxL-height[lo], update maxL, lo++. Else water[hi]=maxR-height[hi], update maxR, hi--.

Complexity

Time

O(n)

Space

O(1)

Single pass, two pointers, constant extra space.

Solution code

Python

def trap(self, height: List[int]) -> int:
    lo, hi = 0, len(height) - 1
    maxL = maxR = water = 0
    
    while lo < hi:
        if maxL <= maxR:
            maxL = max(maxL, height[lo])
            water += maxL - height[lo]
            lo += 1
        else:
            maxR = max(maxR, height[hi])
            water += maxR - height[hi]
            hi -= 1
    
    return water

Edge cases to remember

⚠Empty or single element: return 0

⚠Monotonically increasing/decreasing: no water trapped

Hints

What pattern do you think this problem uses?