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,
Examples:
Input: arr[] = {2, 0, 2}
Output: 2
Structure is like below:
| |
We can trap 2 units of water in the middle gap.
Input: arr[] = {3, 0, 0, 2, 0, 4}
Output: 10
Structure is like below:
|
| |
| | |
|__|_|
Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Structure is like below:
|
| || |
_|_||_||||||
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 tallest height on left side and tallest 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). we can 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:
public class TrappingRainWater {
public static void main(String[] args) {
int arr[] = { 3, 2, 1, 5 };
int arr1[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int arr2[] = { 0, 1, 0, 2, 0, 1, 0 };
int arr3[] = { 2, 0, 2 };
int arr4[] = { 3, 0, 0, 2, 0, 4 };
System.out.println(getMaxRainwaterBetweenTowers(arr));
System.out.println(getMaxRainwaterBetweenTowers(arr1));
System.out.println(getMaxRainwaterBetweenTowers(arr2));
System.out.println(getMaxRainwaterBetweenTowers(arr3));
System.out.println(getMaxRainwaterBetweenTowers(arr4));
}
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;
}
}
// Output:
3
6
2
2
10
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Note: As we pre calculate max height on right side for each bar and keep it handy in additional array (rightGraph), we can similarly pre calculate max height on left side for each bar and keep it handy in additional array (leftGraph).
Pre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element.
So the easiest java program for above problem is as below:
class TrappingRainWaterSolutionUsingStack {
public static void main(String[] args) {
int arr[] = { 3, 2, 1, 5 };
int arr1[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int arr2[] = { 0, 1, 0, 2, 0, 1, 0 };
int arr3[] = { 2, 0, 2 };
int arr4[] = { 3, 0, 0, 2, 0, 4 };
System.out.println(trap(arr));
System.out.println(trap(arr1));
System.out.println(trap(arr2));
System.out.println(trap(arr3));
System.out.println(trap(arr4));
}
// Method for maximum amount of water
static int trap(int[] arr) {
int n = arr.length;
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int left[] = new int[n];
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
int right[] = new int[n];
// Initialize result
int water = 0;
// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++)
left[i] = Math.max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
right[i] = Math.max(right[i + 1], arr[i]);
// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i] .
for (int i = 0; i < n; i++)
water += Math.min(left[i], right[i]) - arr[i];
return water;
}
}
// Output:
3
6
2
2
10
Harshit Jain 
Hello to every one, the contents present at this website are actually
amazing for people knowledge, well, keep up the nice work fellows.
LikeLike
Thanks for your kind words
LikeLike