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