42. Trapping Rain Water

/**
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.


The above 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. Thanks Marcos for contributing this image!

Example:

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

Solution Anlysis:
Runtime: 0 ms, faster than 100.00% of Java online submissions for Trapping Rain Water.
Memory Usage: 37.6 MB, less than 97.95% of Java online submissions for Trapping Rain Water.

Approach:
Start from both left and right depending on which height is smaller, when you get taller height then current height then add it to maxHeight and when you get shorter height then maxHeight then add the difference between maxHeight and shorter height to total water volume.
**/
class Solution {
    public int trap(int[] height) {
     int l=0,r=height.length-1;
	 int maxLeft=0,maxRight=0;
	 int sum=0;
	 while(l<=r){
		 if(height[l]<=height[r]){
			 if(height[l]>=maxLeft)
				 maxLeft=height[l];
			 else
				sum += maxLeft-height[l]; 
		 l++;
		 }
		 else{
			 if(height[r]>=maxRight)
				 maxRight = height[r];
			 else
				 sum +=maxRight-height[r];
			 r--;
		 }
	 }
	 return sum;
    }
}