Thursday 18 August 2016

Trapping Rain Water

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: array[] = {2, 0, 2}
Output: 2
Structure is like below
| |
|_|
Output: 2

Input: array[] = {3, 0, 1, 0, 2, 0, 4}
Structure is like below
      |
|     |
|   | |
|_|_|_|
Output: 12

Approach:
Maximum water on any bar = Min(Max height bar on left, Max height bar on right) – Height of the bar.



Brute force: Time complexity O(n^2).
Dynamic programming: Time complexity O(n).

public class WaterInWarDP {

     private static int length;

     private static int maxWaterInWarDp(int[] barsInSea) {

           /* Maximum water on a bar = Min(Max left height, Max Right height). */

           /* Get Max left array.*/
           int[] maxLeft = getMaxLeftArray(barsInSea);

           /* Get Max Right array.*/
           int[] maxRight = getMaxRightArray(barsInSea);

           int waterOnBars = 0;
           for (int i = 0; i < length; i++) {
                waterOnBars = waterOnBars
                  Math.min(maxRight[i],maxLeft[i])-barsInSea[i];
           }

           return waterOnBars;
     }

     private static int[] getMaxRightArray(int[] barsInSea) {
           int[] maxRight = new int[length];
           maxRight[length-1] = barsInSea[length-1];
           for (int i = length-2; i >=0; i--) {
                maxRight[i] = Math.max(barsInSea[i], maxRight[i+1]);
           }
           return maxRight;
     }

     private static int[] getMaxLeftArray(int[] barsInSea) {
           int[] maxLeft = new int[length];
           maxLeft[0] = barsInSea[0];
           for (int i = 1; i < length; i++) {
                maxLeft[i] = Math.max(barsInSea[i], maxLeft[i-1]);
           }
           return maxLeft;
     }
    
    
     public static void main(String[] args) {
           int[] barsInSea = {3,0,0,2,0,4};
           length = barsInSea.length;
           int maxWater = maxWaterInWarDp(barsInSea);
           System.out.println("Maximum water : "+ maxWater);
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...