Trapping Rain Water between Towers

We have an array where each element represents height of a tower. If it starts raining, what is the amount of water that can be collected between the towers? Assumption is that the width of every tower is 1.
Example:
Input  - {1,5,2,3,1,7,2}
Output - 11


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




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);


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

public class RainWaterBetweenTowers {

    public static int getMaxRainwaterBetweenTowers(int[] towerHeight) {
        int maxSeenSoFar = 0;

        int[] maxSeenRight = new int[towerHeight.length];
        int maxSeenLeft = 0;

        int rainwater = 0;

        for (int i = towerHeight.length - 1; i >= 0; i--) {
            if (towerHeight[i] > maxSeenSoFar) {
                maxSeenSoFar = towerHeight[i];
                maxSeenRight[i] = maxSeenSoFar;
            } else {
                maxSeenRight[i] = maxSeenSoFar;
            }
        }

        for (int i = 0; i < towerHeight.length; i++) {
            rainwater = rainwater + Integer.max(Integer.min(maxSeenLeft, maxSeenRight[i]) - towerHeight[i], 0);
            if (towerHeight[i] > maxSeenLeft) {
                maxSeenLeft = towerHeight[i];
            }
        }

        return rainwater;
    }

    public static void main(String[] args) {
        int[] towerHeight = { 1, 5, 2, 3, 1, 7, 2, 4 };
        System.out.println(getMaxRainwaterBetweenTowers(towerHeight));
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer