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