Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1
The dips between the taller bars hold 6 units of water in total.
Example 2
The insight: for each position, the water sitting above it is
min(highest bar to its left, highest bar to its right) - height[i],
and never less than zero. Computing those two maxima naively is O(n²); two
pointers moving inward gets it in O(n) with O(1) extra space.
Examples
Example 1
- Input:
- [0,1,0,2,1,0,1,3,2,1,2,1]
- Output:
- 6
Water collects in the dips between the taller bars, six units in total.
Example 2
- Input:
- [4,2,0,3,2,5]
- Output:
- 9
The basin between the 4 and the 5 holds nine units.
Example 3
- Input:
- [3,2,1]
- Output:
- 0
A slope traps nothing — there is no taller bar on the right to hold water in.
Constraints
1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5
Run checks your code against the 3 examples. Submit checks it against all 323 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.