How much rain pools between the bars? Walk in from both ends, always moving the side with the lower wall, whose water is already decided.
▼The problem
LeetCode 42 (Hard). Given the heights of a row of bars (each one unit wide), how much rain water is trapped between them? The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i] (counting the bar itself on both sides).
Example: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → 6.
The solution
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max < right_max:
water += left_max - height[left]
left += 1
else:
water += right_max - height[right]
right -= 1
return waterTranscript
Trapping Rain Water. You get a row of bars. When it rains, water pools in the dips between them. How much is trapped?
Take zero, one, zero, two, one, zero, one, three, two, one, two, one. After the rain, six squares of water are trapped.
Look at one bar. Its water rises to the lower of two walls: the tallest bar on its left, and the tallest on its right. Subtract the bar's height, and that's its water.
The simple way scans both sides for every bar. With n bars, that's n squared steps.
Better: put a pointer at each end, and remember the tallest bar each has seen. Always move the side with the smaller maximum. Its water is already decided: the other side has a wall at least as tall.
In code: while the pointers haven't met, update both maximums. If the left one is smaller, add the left bar's water and step inward. Otherwise, do the same on the right.
Let's run it. The pointers step in until the left max is one and the right max is two. Left is lower, so the dip fills: one. Now both maxes are two. On a tie the right side moves: one more. Then the right pointer reaches the three, and the left side does the rest: zero, one, two, one. The pointers meet at the tallest bar. Six squares.
Each bar is visited once, so time is linear, and a few variables mean constant space.
Two pointers, two walls, and the lower one decides. That's Trapping Rain Water.