There are n vertical silo walls standing in a row, wall i having non-negative integer height h[i] and unit width. After a rainstorm, water settles above each wall position, rising up to the smaller of the tallest wall to its left and the tallest wall to its right (water cannot rise above the row's outer boundary). Compute the TOTAL volume of water trapped across the entire row.
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the wall heights.
A single integer: the total volume of water trapped.
Example 1
Input
5 4 1 3 1 5
Expected
7
Explanation
Above each wall the trapped water is 0, 3, 1, 3, 0 (bounded by min(left max, right max) minus the wall's own height), totaling 7.
Example 2
Input
3 5 5 5
Expected
0
Explanation
The walls are flat, so no water can be trapped: the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →