Trapping Rain Water
Part of Practice: Walls & Water
You are given an elevation map: an array where each value is the height of a bar of width 1. After it rains, water settles in the dips between taller bars. Return the total number of unit squares of water the terrain traps.
The array can hold up to 20,000 bars with heights up to 100,000. Water held above any position is limited by the tallest bar somewhere to its left and the tallest somewhere to its right — whichever of those two is lower sets the water surface there.
Examples
- Input:
- height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
- Output:
- 6
Water collects in the valleys: 1 unit over index 2, 1 over index 4, 2 over index 5, 1 over index 6, and 1 over index 9 — 6 units total.
- Input:
- height = [4, 2, 0, 3, 2, 5]
- Output:
- 9
Between the walls of height 4 and 5, the columns hold 0+2+4+1+2+0 = 9 units.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.