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);

     }

}