Description
Given nonnegative heights of unit-width bars, compute the total water retained after rain. Water above a bar is limited by the tallest boundary on each side.
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 waterExamples
Example 1
- Input
[[0,1,0,2,1,0,1,3,2,1,2,1]]- Output
6
Six unit squares fit between the bars.
Example 2
- Input
[[3,0,3]]- Output
3
The middle position holds three units.
Example 3
- Input
[[1,2,3]]- Output
0
A rising slope cannot trap water.
Approach
Walk inward from both ends while tracking each side's highest bar. Advance the side with the smaller maximum: its boundary already determines the water at that position. Add the boundary height minus the current bar.
Time & space
O(n) time and O(1) auxiliary space, where n is the number of bars.