-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtrappedWater.java
More file actions
26 lines (26 loc) · 985 Bytes
/
Copy pathtrappedWater.java
File metadata and controls
26 lines (26 loc) · 985 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class trappedWater {
public static int trappedWater(int height[]) {
//calculate leftmax boundary
int leftmax[] = new int[height.length];
leftmax[0] = height[0];
for(int i=1; i<height.length; i++) {
leftmax[i] = Math.max(height[i], leftmax[i-1]);
}
//calculate rightmax boundary
int rightmax[] = new int[height.length];
rightmax[height.length - 1] = height[height.length-1];
for(int i = height.length-2; i>=0; i--) {
rightmax[i] = Math.max(height[i], rightmax[i+1]);
}
int trappedWater = 0;
for(int i=0; i<height.length; i++) {
int waterlevel = Math.min(leftmax[i], rightmax[i]);
trappedWater += waterlevel - height[i];
}
return trappedWater;
}
public static void main(String[] args) {
int height[] = {4,2,0,6,3,2,5};
System.out.println("trapped water is : " +trappedWater(height));
}
}