Trapping rain water algorythm

trapping_water.java

Problem
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.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The below elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.



Program Structure:
public class Solution {
    public int trap(int[] height) {
        
    }
}
Solution
Keep track of the maximum height from both forward directions backward directions, call them leftmax and rightmax.

public class Solution {
  public int trap(int[] A){
    int a=0;
    int b=A.length-1;
    int max=0;
    int leftmax=0;
    int rightmax=0;
    while(a<=b){
      leftmax=Math.max(leftmax,A[a]);
      rightmax=Math.max(rightmax,A[b]);
      if(leftmax<rightmax){
        max+=(leftmax-A[a]);       // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
        a++;
      }
      else{
        max+=(rightmax-A[b]);
        b--;
      }
    }
    return max;
  }
}
Difficulty: Hard