Q23: Trapping Rain Water. - DSA Patterns (Multi-Lang)

In Simple Words: Maintain maxLeft and maxRight with two pointers. Whichever boundary is lower limits water level: add maxLeft - height[l] and advance l, or maxRight - height[r] and decrement r.

Time: $O(N)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

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