Trapping rain water
Coding problemHardAsked in: Adobe, Amazon, Flipkart, Goldman Sachs, Google, Microsoft
A row of bars has the heights given in the list, each bar one unit wide. After heavy rain, water collects in the dips between taller bars. Return the total units of water held.
Above each bar the water rises to the lower of the tallest bar on its left and the tallest bar on its right, minus the bar's own height (never below 0). The total can be larger than a 32-bit integer can hold.
Examples
Example 1
Input: heights = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Example 2
Input: heights = [4,2,0,3,2,5]
Output: 9
Example 3
Input: heights = [1,2,3]
Output: 0
No bar has a taller bar on both sides.
Constraints
- The list holds between 0 and 100,000 values
- Each height is between 0 and 100,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.