Find rain water volume stored in the blocks.
// This problem is taken from #Leetcode
// the heights of blocks are given in an array {0,1,0,3,2,1,0,1,3,0,5,1,2,1} and width =1. Find the volume(unit blocks) of rain water collected.
//Get max of left to right
//Get max of right to left
//Get min of above two max at each index/unit and then subtract the height of each unit
//Sum the index values
package abc;
import java.util.Arrays;
public class UnitOfRainWater {
public static void main(String[] args) {
int[] num = {0,1,0,3,2,1,0,1,3,0,5,1,2,1};
int l = num.length;
int waterTrappedUnit = 0;
//left to right, finding max height
int[] maxLeft = new int[l];
int leftMax = 0;//max left will be zero because there is nothing to the left of it
for(int i = 1;i<l;i++) {
leftMax = Math.max(leftMax,num[i-1]);
maxLeft[i]=Math.max(leftMax, num[i]);
}
System.out.println("MaxLeft="+Arrays.toString(maxLeft));//[0, 1, 1, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5]
//right to left, finding max height
int[] maxright = new int[l];
int rightMax = 0;
for(int i = l-2;i>=0;i--) {
maxright[0]=0;//max right will be zero because there is nothing to the right of it
rightMax = Math.max(rightMax,maxright[i+1]);
maxright[i]=Math.max(rightMax, num[i]);
}
System.out.println("MaxRight="+Arrays.toString(maxright));//[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 2, 2, 0]
//Water Level
int waterArea = 0;
int[] waterLevel = new int[l];
for(int i = 1;i<l-1;i++) {//ignore leftmost and rightmost values
waterLevel[i] = (Math.min(maxLeft[i], maxright[i]))-num[i];//the -num[i] is for the size of the each pillor.
waterArea = waterArea+waterLevel[i];//width =1
}
System.out.println("waterStored by each unit ="+Arrays.toString(waterLevel));//[0, 0, 1, 0, 1, 2, 3, 2, 0, 3, 0, 1, 0, 0]
System.out.println("Total water ="+waterArea);//13
}
}
Output:
MaxLeft=[0, 1, 1, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5]
MaxRight=[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 2, 2, 0]
waterStored by each unit =[0, 0, 1, 0, 1, 2, 3, 2, 0, 3, 0, 1, 0, 0]
Total water =13