//Runtime: 1 ms, faster than 98.11% of Java online submissions for Trapping Rain Water.
//Memory Usage: 37.4 MB, less than 98.63% of Java online submissions for Trapping Rain Water.
class Solution {
  public int trap(int[] height) {
    int volume = 0;
    if(height == null || height.length == 0) return volume;

    int left = 0, leftMax = 0;
    int right = height.length-1, rightMax = 0;

    while(right > left){
      leftMax = Math.max(leftMax, height[left]);
      rightMax = Math.max(rightMax, height[right]);
      if(leftMax < rightMax){
        int col = leftMax - height[left];
        if(col > 0)  volume += col;
        left++;
      }else{
        int col = rightMax - height[right];
        if(col > 0) volume += col;
        right--;
      }
    }
    return volume;
  }
}