The tell: Water held above each position, bounded by the tallest bar on each side.
How you get there
1Water above i is min(max left of i, max right of i) − height[i].
2Carry running maxima from both ends instead of precomputing two arrays.
3Advance the pointer on the smaller side — its running max is then known to be the binding one.
Solution
Python
def trap(height: list[int]) -> int:
if not height:
return 0
lo, hi = 0, len(height) - 1
left_max, right_max = height[lo], height[hi]
total = 0
while lo < hi:
if left_max <= right_max:
lo += 1
left_max = max(left_max, height[lo])
total += left_max - height[lo]
else:
hi -= 1
right_max = max(right_max, height[hi])
total += right_max - height[hi]
return total
Time
O(n)
Space
O(1)
What goes wrong
Adding water before updating the running max produces negative contributions at new peaks.