http://www.technicalpage.net/search/label/SQL

RainWaterCollectionInJava

 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

 

 

No comments:

Post a Comment