SeniorSenior (6–10 yrs)CodingPythonAmazonGoldman SachsGoogle

Trapping Rain Water

Given elevation map heights[i], compute how much water it can trap after raining.

Answers use simple, clear English.

Time: O(n)Space: O(1)

Quick interview answer

Two-pointer: move the side with smaller height, accumulating water from left_max/right_max. Alternative: precompute left/right max arrays. O(n) time.

Detailed answer

Two-pointer: move the side with smaller height, accumulating water from left_max/right_max. Alternative: precompute left/right max arrays. O(n) time. Stack-based next-greater also works for an O(n) solution.

Full explanation

Stack-based next-greater also works for an O(n) solution.

Real example & use case

Civil simulation estimating retained volume between terrain spikes.

Pros & cons

Pros: two-pointer O(1) space. Cons: harder to see than prefix-max version.

Code example

def trap(height: list[int]) -> int:
    lo, hi = 0, len(height) - 1
    left_max = right_max = water = 0
    while lo <= hi:
        if height[lo] <= height[hi]:
            left_max = max(left_max, height[lo])
            water += left_max - height[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            water += right_max - height[hi]
            hi -= 1
    return water

Practice code · python (view only · no execution)

def trap(height: list[int]) -> int:
    lo, hi = 0, len(height) - 1
    left_max = right_max = water = 0
    while lo <= hi:
        if height[lo] <= height[hi]:
            left_max = max(left_max, height[lo])
            water += left_max - height[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            water += right_max - height[hi]
            hi -= 1
    return water

#two-pointers#hard