Trapping Rain Water

Scan both sides

At position i, water rises only as high as the shorter of the tallest bars to its left and right. Scan both directions to find those two boundaries, then subtract height[i].

def trap(height: list[int]) -> int:
    total = 0
    n = len(height)
 
    for i in range(n):
        left_max = 0
        for left in range(i + 1):
            left_max = max(left_max, height[left])
 
        right_max = 0
        for right in range(i, n):
            right_max = max(right_max, height[right])
 
        total += min(left_max, right_max) - height[i]
 
    return total

Including the current bar in both scans keeps the contribution non-negative. The answer is correct, but almost every boundary gets rediscovered many times.

Time O(n²) — each of n positions may scan the whole map. Space O(1) — only the two maxima and the running total are stored.

Converging pointers + maxima

Move left and right inward while carrying the tallest bar seen from each side. If height[left] <= height[right], the right side already has a boundary at least as tall as the current left bar. That makes the left position safe to settle:

• If height[left] reaches a new left_max, it holds no water.
• Otherwise, it holds left_max - height[left] units.

When the right bar is lower, the same reasoning settles the right position using right_max.

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

Each decision finalizes one position. You never need to revisit it because the lower side's available boundary — not the unknown interior — is what limits that position.

Time O(n) — one pointer moves on every iteration. Space O(1) — four indices or running values are enough.