## Algorithm/Insights

1. For each tower, we try to figure out if there is some unit of rainwater above it, if yes, then what is the amount.

2. Keep adding rainwater amount contribution by each tower to get total rainwater for given set of towers.

Question: For a tower, how can we figure out if there is some unit of rainwater on it?

Solution: Try visualizing the scenario. For rainwater to be on a tower, the height of tower should be less than (one of the tower on its left && one of the tower on its right).

Question: For current tower in consideration, why its height should be less than height of at least one tower on its left for it to contain some unit of water on top of it?

Solution: Consider Tower 2 in the figure, we can easily visualize that since there is no tower on its left which has more height than it, hence Tower 2 will not contain any rainwater on top of it. Similarly current tower's height should be less than height of at least one tower

on its right for it to contain some unit of water on top of it.

Question: With the previous assumption that the height of current tower is less than one of the tower on its left && one of the tower on its right (for it to have rainwater on top of it), what is the maximum amount of rainwater on top of current tower?

Solution: Let us try to visualize the solution using Tower 5. We can easily visualize that 4 unit of water is on top of Tower 5. How did we arrive at this solution? If we look closely, we arrived at solution by first looking on the left of Tower 5 and finding out max height on left side which is Tower 2, and then looking on the right of Tower 5 and finding out max height which is Tower 6. Finally minimum(Tower 2 , Tower 6) - Tower 5 gave our solution which is 4 unit of water.

Hence we arrive at our solution:

maxAmountOfRainWaterOnCurrentTower = 0 (there is no tower on left of current tower with more height || there is no tower on right of current tower with more height)

= (Min(MaxHeightOfTowerOnLeft, MaxHeightOfTowerOnRight) - currentTowerHeight)

Joining above conditions:

maxAmountOfRainWaterOnCurrentTower = Max(Min(MaxHeightOfTowerOnLeft, MaxHeightOfTowerOnRight) - currentTowerHeight, 0);

Algorithm:

1: With given towerHeight array, create 2 arrays, maxSeenRight and maxSeenLeft.

maxSeenLeft[i] - max height on left side of Tower[i].

maxSeenRight[i] - max height on right side of Tower[i].

2: Calculate for each tower:

rainwater = rainwater + Max(Min(maxSeenLeft[i], maxSeenRight[i]) - towerHeight[i], 0);