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.

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.

Input = [2, 0, 2]

Output = 2

Input = [3, 0, 0, 2, 0, 4]

Output = 10

Input = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output = 6

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.

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.

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,

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.

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.

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???So the amount of water a bar hold = Minimum among( max on left side, max on right side) - current bar height

### 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,

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

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

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.**

## Post a Comment