Loading...
Loading...
Loading...
A row of n hostel buildings of width 1 metre stands side by side, with no gaps. Building i has height h[i] metres. After heavy rain, water collects in the dips between taller buildings. Above building i, water rises up to the smaller of the tallest building on its left side and the tallest building on its right side, counting building i itself. Print the total amount of water held, in square metres of this side view.
Example
Input
12 0 1 0 2 1 0 1 3 2 1 2 1
Output
6
Water sits above buildings 3, 5, 6, 7 and 10: 1 + 1 + 2 + 1 + 1 = 6.
Try the problem first. Open one hint at a time.
For each building, the water above it is min(tallest on the left, tallest on the right) − its own height.
Computing the two maximums for every building by scanning is O(n²). Try to find them while walking inward from both ends.
Keep leftMax and rightMax. If leftMax is smaller, the left building is limited by leftMax, whatever lies further right. Settle it and move the left index.
Otherwise settle the right building with rightMax. Add each amount to a long total.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor