JavaScriptHardTwo Pointers35 min
Compute trapped rain water
Treat the array as unit-width nonnegative bar heights and return the total amount of rain water trapped between bars. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess resolve the side with the smaller established boundary maximum.
Input
A JSON array of integers on stdin.
Output
Print one compact JSON value: an integer volume.
Constraints
0 <= array length <= 10000; integer heights between 0 and 1000000.
Example
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Example 2 input
[3,0,3]
Output
3
Boundary case: Monotone heights do not trap water
Public test cases (2)
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Expected output
6
Input
[4,2,0,3,2,5]
Expected output
9
Hints (2)
- Water depth is limited by the smaller enclosing boundary
- Monotone heights do not trap water
Target complexity: time O(n) · space O(1)