Trapping Rainwater Problem: Logic Building

So this problem goes like this, given a bunch of heights(visualise a bar graph) calculate the volume of water trapped between these bars.

The dotted lines represent where the water is going to be trapped.

Now let us build the logic for solving this problem.

Case1 :: Only one height is given : In this case no water will be trapped.

Case2 :: Two heights are given : In this case also no water will be trapped…Think about this carefully :)

So now we arrive at the conclusion that more than 2 heights should exist to trap water.

Also notice that ascending and descending distributions won’t trap any water either. Thus we need to have like a certain depth between 2 bars to trap water.

Here observe that the second graph(right) has the ability to trap water as it has certain depth between bars.

So in order to find the trapped water for each bar, we will need to find the leftmost and rightmost bars that hold water, i.e the left most maximum boundary and right most maximum boundary. The water level will be the minimum of these 2. EX: Refer to the right graph in image2, for the bar of height 4 the leftmost maximum boundary is 5 and rightmost maximum boundary is 6.
Thus the minimum of these 2 is 5 and the water level will be 5 (since if it was 6 it would overflow on the left side).

After finding these boundaries we can easily calculate the amount of trapped water by using the formula
Trapped water in each bar=( waterlevel-height of the bar)*width
(Note that the width is assumed to be 1 unless stated otherwise in the question).

We will need to sum the water trapped by each bar to get the total volume of the water trapped.

Let us now calculate the volume of water for the distribution in image1 with this method.
bar1: trapped water=0(since there is no other bar on the left side, it won’t hold any water)
bar2: trapped water=min(leftmost max boundary, rightmost max boundary)-height=min(5,6)-3=5–3=2
bar3:trapped water=min(5,6)-0=5
bar4:trapped water=0(won’t hold any water since it will spill on both sides)
bar5:trapped water=min(6,4)-2=2
bar6:trapped water=min(6,4)-1=3
bar7:trapped water=0(since there is no bar on the right side, it cannot hold any water)

Thus the total volume of the trapped water=0+2+5+0+2+3=12

Now that logic is built, coding this becomes simpler….The only thing left for you to now figure out is finding the leftmost and rightmost maximum boundary since it unfortunately does not come intuitively to computers like to us humans. Hint : You can use helper arrays :)