Here is an image explaining the situation

The blue squares are the water trapped and the black are the bars trapping the water, the green numbers are the array values representing the heights.

The key observation here is that the max height bar will trap water depending on the max bars (relative to it self) on its right and left side.

Another observation is that the bar at location 'i' will trap water (minimum of [highest bar on right, higiest bar on left] - my own height) of water.

So here what we need to do:

- for each bar:
- find the height of the highest bar on the right
- find the height of the highest bar on the left
- total = min(rightmax, leftmax) - my height

for an index and onwards

Code: Select all

```
for(int i=0;i<height.length;i++) {
curMax = Math.max(height[i], curMax);
leftMax[i] = curMax;
}
```

Code: Select all

```
2,1,2,1,3,0,2,1,3
```

Code: Select all

```
2,2,2,2,3,3,3,3,3
```

now just apply the algorithm above:

Code: Select all

```
public int trap(int[] height) {
int[] leftMax = new int[height.length];
int[] rightMax = new int[height.length];
int curMax = -1;
for(int i=0;i<height.length;i++) {
curMax = Math.max(height[i], curMax);
leftMax[i] = curMax;
}
curMax = -1;
for(int i=height.length-1;i>=0;i--) {
curMax = Math.max(height[i], curMax);
rightMax[i] = curMax;
}
int sum = 0;
for(int i =0;i<height.length;i++) {
sum += Math.min(rightMax[i], leftMax[i]) - height[i];
}
return sum;
}
```