Trapping Rain Water

Signal

Water trapped at any position is bounded by the shorter of the tallest bar to its left and the tallest bar to its right — a "bounded by the min of two running maxima" shape. Whenever a quantity at each position depends on a prefix max and a suffix max simultaneously, that's the two-pointer-with-running- maxima pattern, and it's the hardest member of this pattern family — expect it at solo.

Approach

The brute force computes, for every index, the max to its left and the max to its right, and takes min(left_max, right_max) - height[i]. That needs two full passes (or two arrays) of precomputed maxima. The two-pointer version collapses this into one pass: walk left and right inward, and at each step process whichever side currently has the smaller running max — because on that side, the running max is guaranteed to be the true bound (the far side is provably taller), so you can settle that position's water immediately without knowing the far side's exact maximum, only that it's at least as big.

Skeleton

left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
    if height[left] < height[right]:
        left_max = max(left_max, height[left])
        water += left_max - height[left]
        left += 1
    else:
        right_max = max(right_max, height[right])
        water += right_max - height[right]
        right -= 1

Solution

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

Complexity

O(n) time, one pass. O(1) space — this is the upgrade over the O(n)-space two-array prefix/suffix-max version, which is a fine stepping stone to derive this from out loud before coding it.

Pitfalls

• Missing why the smaller-max side is safe to settle immediately — without that argument this looks like it shouldn't work, and it's the first thing an interviewer will ask you to justify.
• Updating left_max/right_max after adding to water instead of before — you'd credit a bar with trapping water above its own height.
• Defaulting to the O(n)-space prefix/suffix-max arrays and stopping there when asked for the follow-up — that solution is a fine first cut, but know the O(1)-space two-pointer refinement above.