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.

Example:

```Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6```

## Solution

```public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}

int result = 0;
// leftMax represents the highest bar from left
int leftMax = Integer.MIN_VALUE;
// rightMax represents the highest bar from right
int rightMax = Integer.MIN_VALUE;

// use two pointers to scan the entire array until they meet with each other
// Key points: any bars in the middle of leftMax bar and rightMax bar will not influence
// how much water can current position trap
for (int left = 0, right = height.length - 1; left <= right;) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);

//how much can current position trap depends on the shorter bar
if (leftMax < rightMax) {
//DO NOT FORGET to subtract bar height of current position
result += leftMax - height[left];
left++;
}
else {
result += rightMax - height[right];
right--;
}
}
return result;
}
```