Hard
Trapping Rain Water
- Time limit
- 3 s
- Memory limit
- 256 MB
- Estimated
- 20 min
- Two Pointers
Description
Description
You are given an array height representing an elevation map, where height[i] is the height of the bar at position i and each bar has width 1. Compute how much rainwater the terrain can trap after it rains.
Examples
Example 1
- Input:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] - Output:
6
Example 2
- Input:
height = [4, 2, 0, 3, 2, 5] - Output:
9
Example 3
- Input:
height = [1, 1, 1] - Output:
0
Expected Function Behavior
Implement trap(height) and return the total units of trapped water.
Constraints
0 <= height.length <= 1000000 <= height[i] <= 100000
Sample cases
3Sample 1
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Expected output
6
Sample 2
Input
height = [4,2,0,3,2,5]
Expected output
9
Skills and languages
Patterns
- Two-Pass Greedy
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer