Trapping Rain Water
Advanced
heights[i] is the height of a bar of width 1. After it rains, water collects between the bars. Return the total amount of water trapped.
For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] the answer is 6.
The starter code searches both sides of every bar. It is correct but too slow for many bars.
Examples
Example 1
Input:
trap_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
Output:
6
Example 2
Input:
trap_water([4, 2, 0, 3, 2, 5])
Output:
9
Constraints
0 <= len(heights) <= 2000000 <= heights[i] <= 10**5
Theory
Go to TheoryKeywords
dsa-sheettwo-pointerstwo-pointers
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.