the trick
Water over column i is min(maxLeft, maxRight) − height[i]. You never need both full prefix arrays. Advance the pointer on the smaller side, because that side's max is the binding constraint.
The question behind the question
Given bar heights, how much water sits on top after rain? The whole problem is
one observation: the water above column i is bounded by the shorter of the
tallest wall to its left and the tallest wall to its right.
water[i] = min(maxLeft[i], maxRight[i]) - height[i]
Brute force, then the cut
The naive version recomputes maxLeft and maxRight for every i. That's
O(n²). The first real optimization is to precompute both as prefix/suffix
arrays, which gets you to O(n) time but O(n) space.
The trick is realizing you don't need to store either array. Walk two pointers inward. Whichever side has the smaller running max is the side that decides how much water the current column holds; so it's safe to settle that column and move that pointer.
def trap(height: list[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
max_left, max_right = height[left], height[right]
water = 0
while left < right:
if max_left <= max_right:
left += 1
max_left = max(max_left, height[left])
water += max_left - height[left]
else:
right -= 1
max_right = max(max_right, height[right])
water += max_right - height[right]
return waterWhy advancing the smaller side is provably safe
When max_left <= max_right, the left column's water is capped by max_left
no matter what taller walls exist to the right. The right side is already at
least as tall, so it can't be the binding constraint. That guarantee is what
lets us commit the column and discard the rest of the right side from
consideration. The symmetric argument holds when the right max is smaller.
O(n) time, O(1) space, single pass.