137. Rain Between Walls
A city skyline is modelled as a row of walls, each one unit wide. The array heights gives the height of the wall at every position, and the ground below the walls is perfectly flat and watertight.
After a heavy rainfall, water collects in the dips between taller walls. A position can hold water up to the height of the shorter of the tallest wall somewhere to its left (itself included) and the tallest wall somewhere to its right (itself included), and the water above that position is that level minus the position's own height. Water that would run off either end is lost. Return the total number of units of water that remain trapped over the whole row.
Example 1
- Input:
- heights = [3,0,2,0,4]
- Output:
- 7
- Explanation:
Position 1 holds min(3,4)-0=3, position 2 holds min(3,4)-2=1 and position 3 holds min(3,4)-0=3. Total 3+1+3=7.
Example 2
- Input:
- heights = [2,5,1,2,3,4,7,7,6]
- Output:
- 10
- Explanation:
Between the walls of height 5 and 7 the levels are 5, so the dips hold 4+3+2+1=10 units. Positions at the ends hold nothing.
Example 3
- Input:
- heights = [1,2,3,4]
- Output:
- 0
- Explanation:
Heights only rise, so water would run off the left side everywhere. Nothing is trapped.
Constraints
1 ≤ heights.length ≤ 105
0 ≤ heights[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)