Trapping Rain Water

Given bar heights, compute how much water the gaps trap after rain. Water sits above a bar only when higher bars exist on both sides — the trapped amount at index i is min(max_left, max_right) - height[i].

The key insight: you do not need both maxima in full. Two pointers walk inward from the ends, tracking the running max on each side. When the left max is smaller, the left pointer's water level is already decided by max_left — the right side cannot lower it — so the machine charges water there and moves left in. Otherwise it charges the right side. Each bar is visited exactly once, and no per-index right-max scan is needed.

Approach in steps:

1. l = 0, r = n - 1, track max_l and max_r.
2. Move the side with the smaller max; add max_side - height[i] when positive.
3. Sum and return.

def trap(height):
    l, r = 0, len(height) - 1
    max_l = max_r = total = 0
    while l <= r:
        if max_l <= max_r:
            max_l = max(max_l, height[l])
            total += max_l - height[l]
            l += 1
        else:
            max_r = max(max_r, height[r])
            total += max_r - height[r]
            r -= 1
    return total

Time is O(n), space O(1). A monotonic-stack variant (O(n) space) is a common alternative.

Trickiest edge case: descending or ascending ramps trap nothing — [3,2,1] must return 0, which the max-tracking naturally yields since the trailing side never has a higher bar. Equal-height plateaus also trap zero; the <= tie-break direction is arbitrary but must be consistent.