Trapping Rain Water
HardWater held between bars of varying heights
Water sits on top of each bar up to the shorter of the tallest walls on its left and right.
The idea
Water above a bar is bounded by the shorter of the tallest wall to its left and right. Walk inward from both ends, always advancing the side with the smaller running max — that side's bound is known.
The trick
- The shorter wall is always the limiting factor, so it's safe to finalize that column's water.
0
1
0
2
1
0
1
3
2
1
2
1
0
1
2
3
4
5
6
7
8
9
10
11
Step 1 of 14. Brute force: for each bar, find the tallest wall to its left and right. Values: 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1.
1/14
Brute force
timeO(n²)spaceO(1)
Tallest wall each side.
1// for each bar, tallest wall on left and right2for (let i = 0; i < n; i++) {3 const L = max(h[0..i]), R = max(h[i..n-1]);4 water += Math.min(L, R) - h[i];5}Input
- array
- [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Memory
- i
- —
- left
- —
- right
- —
Output
- water
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
- Output:
- 6
- Explanation:
- Dips between tall bars hold 6 units.
Example 2
- Input:
- height = [4, 2, 0, 3, 2, 5]
- Output:
- 9
- Explanation:
- The valley traps 9 units of water.
Example 3
- Input:
- height = [3, 2, 1]
- Output:
- 0
- Explanation:
- A downhill slope traps nothing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.