Trapping Rain Water

Problem

Given an array of non-negative bar heights, each one unit wide, compute how much water can be trapped between the bars after it rains.

Approach

The water above any bar equals the smaller of the tallest bar to its left and the tallest bar to its right, minus the bar's own height.

Two pointers find this without precomputing both maximums. Move inward from whichever side is lower. On that side, the tallest bar seen so far is the binding limit, because the other side is known to have something at least as tall.

Add the difference between that running maximum and the current bar, then step inward.

Solution

class Solution:
    def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        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

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

Edge cases

• Fewer than three bars cannot trap water.
• Strictly rising or falling heights trap nothing.
• Prefix and suffix maximum arrays give the same answer with O(n) extra space.