Trapping Rain Water between Towers

How Much Water Can A Bar Graph Hold 

---

Given an bar graph, encoded as an array of non-negative integers, calculate the units of water that this bar graph can hold.

Let us put in technical terms,
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Lets understand the problem statement graphically and it will be more clear,

Case 1:
Input     = [2, 0, 2]
Output  = 2


Case 2:
Input     = [3, 0, 0, 2, 0, 4]
Output  = 10

Case 3:
Input     = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output  =  6

Algorithm

---

For water to get collected on Bar B, There should be Bar on Left side and Right Side of Bar B whose height is greater than Bar B height otherwise water will overflow.


So for each bar, We can find amount of water it will store by checking the max heights of bars on left and right sides.

Once the bar with max height on left side and max height on right side is evaluated.
Check the minimum among both as that will be the level in which water will be accumulated and rest water will overflow.

So the amount of water a bar hold = Minimum among( max on left side, max on right side) - current bar height

For each bar if we calculate Max height on Left side and Max height on Right side then Time complexity of this solution will be O(n^2). Can we improve here???

Optimization

---

For solving the problem, we need to traverse the given graph heights one by one from Left to Right, 

While traversing from Left to Right, we can keep track of Graph with max height on Left side, but How to get Graph with Max height on Right side?

For Graph with Max height on Right side, We will pre calculate max height on right side for each graph and keep it handy in additional array.


So we will iterate array twice, 

1. one for populating array which stores max height on right side
2. second for calculating amount to water each bar can trap.

Once we have Max graph height array ready which stores max height available on Right side of Graph.

we can start iterating each Graph from Left to Right and apply our above formula for calculating amount of water that can be stored in each Graph.

Trapping Rain Water Java Program

---

package javabypatel;

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

 public static int getMaxRainwaterBetweenTowers(int[] towerHeight) {
  
  int[] maxSeenSoFarFromRight = new int[towerHeight.length];
  
  //Populate maxSeenSoFarFromRight array.
  maxSeenSoFarFromRight[towerHeight.length-1] = towerHeight[towerHeight.length-1];   
  for (int i = towerHeight.length-2; i >= 0; i--) {
   maxSeenSoFarFromRight[i] = Math.max(maxSeenSoFarFromRight[i+1], towerHeight[i]);
  }

  int totalWaterCollection = 0;
  
  int maxSeenSoFarFromLeft = 0;
  for (int i = 0; i < towerHeight.length; i++) {
   if(maxSeenSoFarFromLeft < towerHeight[i]){
    maxSeenSoFarFromLeft = towerHeight[i];
   }
   int minFromLeftRight = Math.min(maxSeenSoFarFromLeft, maxSeenSoFarFromRight[i]);
   totalWaterCollection += (minFromLeftRight - towerHeight[i]);
  }
  return totalWaterCollection;
 }
}

You may also like to see

---

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.