Water held between the bars

A row of bars stands side by side, each one unit wide, with the heights given. After heavy rain, water settles in the dips. Report how many units of water are held.

Worked example#

For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

       #    
   #~~~##~# 
 #~##~######

The ~ marks are water. Adding them up gives 6.

The idea#

Look at one bar at a time and ask how deep the water is above it. Water above a bar is held in by the tallest bar somewhere to its left and the tallest somewhere to its right. The shorter of those two walls decides the level, and the water above this bar is that level minus the bar's own height:

water[i] = min(tallest to the left, tallest to the right) - height[i]

Never negative, because one of the two walls is the bar itself in the worst case.

Computing both maxima for every bar separately costs two extra arrays. There is a neater way with two pointers walking inwards. At each step, look at whichever end is shorter. That side's answer is already decided: the other end is taller, so there is guaranteed to be a wall at least that high on the far side, and the near maximum is the one that limits the water. So you can settle that bar and step inwards, keeping only two running maxima.

Constraints#

• 1 <= n <= 100000
• 0 <= height[i] <= 100000