Container With Most Water, Trapping Rain Water

Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Solution

Two Pointers l and r:

start from two ends, keep updating maxsofar area

changing rule: if left’<’right then we know moving right makes no change(width decreases and min board is still left), so we need to move left pointer, vise versa

public int maxArea(int[] height) {
     if(height==null) return -1;
     int curmax=-1, maxsofar=-1, l=0,r=height.length-1;
     while(l<r){
      curmax=(r-l)*Math.min(height[l],height[r]);
      if(curmax>maxsofar){
        maxsofar=curmax;
      }
      if(height[l]<height[r]){
        //move r-- would never increase area with same l
        int tmp=height[l];
        while(l<r && height[l]<=tmp)
        l++;
      }
      else{
        int tmp=height[r];
        while(l<r && height[r]<=tmp)
        r--;
      }
     }
     
     return maxsofar;
     
 }

---

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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Crazy Smart Solution

left[i] to store the largest to the left of i; right[i] to store the largest to the right of i. The min of these two, subtracted by A[i], determines how much water A[i] can hold
remember to add up volume from 1 to n-2, since two sides cannot hold water.

public int trap(int[] A) {
      if (A == null || A.length == 0) {  
          return 0;  
      }  
      int i, n=A.length,vol=0,max=0,left[]=new int[n],right[]=new int[n];
      //left to right
      for(i=1, max=A[0], left[0]=A[0]; i<n;i++ ){
          if(A[i]>max) {max=A[i]; left[i]=A[i];}
          else left[i]=max;
      }
      //right to left
      for(i = n-2, max=A[n-1],right[n-1]=A[n-1];i>=0;i--){
          if(A[i]>max){max=A[i]; right[i]=max;}
          else right[i]=max;
      }
      for(i =1;i<n-1;i++){
          int tmp= 1 * (Math.min(left[i],right[i])-A[i]);
          if(tmp!=0) vol+=tmp;
      }
      return vol;
  }