You are given a list height of non-negative integers: the heights of bars of width 1 standing
side by side. Rain falls on them and settles in the dips.
Above position i, water rises to the lower of two heights: the tallest bar from the start up to
i, and the tallest bar from i to the end. The water above i is that level minus
height[i]. Return the total amount of water trapped.
Example 1
- Input
- height = [3, 0, 2, 0, 4]
- Output
- 7
Example 2
- Input
- height = [0, 2, 0, 1, 0, 3, 1, 0, 2]
- Output
- 8
Example 3
- Input
- height = [5, 4, 3]
- Output
- 0
Constraints
heightholds 1 to 2 × 10⁴ numbers.- Every height is between 0 and 10⁵.
Show the pattern
Two pointers
The water above a bar is set by the tallest bar on each side. Two pointers moving in from the ends always know which side's maximum is the limit, so one pass with O(1) memory is enough.
See two pointers in a visualiserShow the approach
The water above position i is min(tallest from the left, tallest from the right) − height[i],
counting bar i itself on both sides. Two pointers find it without storing those maxima.
Keep left and right at the ends, with leftMax and rightMax, the tallest bars each pointer
has seen. At each step, move the pointer standing at the lower bar. Say
height[left] < height[right]. Every bar left has passed was lower than some bar on the right
(that's why left moved), so the right side has a bar at least leftMax tall, and the level at
left is just leftMax. Update leftMax with height[left], add leftMax − height[left], and
step left on. The other case is the mirror image.
Time: O(n) · Space: O(1)