42. Trapping Rain Water Leetcode Java

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 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!

Solution:

Two pointers: left and right.

Assume if A[left]<A[right], undoubtedly,  each bar that is smaller than A[left] between left and right can trap at least A[i]-A[left] of water. The way to update the constrains is to increment left pointer till A[newLeft]>A[left], during this process, each bar between the left and newLeft will trap water with A[i]-A[left]. Notice in this case decrementing right pointer wont't give us the right answer, eg, in the example shown in the picture, if left now is A[0]=1, right is A[6]=3, A[5] can trap 1 water rather than 0 because there is a higher left bar which is A[2]=2. In the other way, if A[right]> A[left], then update right pointer and update the total water that was trapped.

Time complexity: O(n)

 public int trap(int[] A) {  
    if(A==null || A.length<=2) return 0;  
    int res=0;  
    int l=0;  
    int r=A.length-1;  
    int min=Math.min(A[l],A[r]);  
    while(l<=r){  
      if(A[l]>min && A[r]>min) min=Math.min(A[l],A[r]);  
      if(A[l]<=min){  
        res+=min-A[l];  
        l++;  
      }  
      else{  
        res+=min-A[r];  
        r--;  
      }  
    }  
    return res;  
   }