Java

ContainerWithMostWater.java

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

public class Solution {
    public int maxArea(int[] height) {
     if (height==null || height.length<2){
         return 0;
     }
     int maxArea=0;
     
     int left=0;
     int right=height.length-1;
     // two pointers scan from two sides to middle
     while (left <right){
         int area=Math.min(height[left], height[right])*Math.abs(left-right);
         
         if (maxArea<area){
             maxArea=area;
         }
         // because the area is decide by the shorter edge
         // so only way to increase the area is to increase the
         // shorter edge
    
         if (height[left]<height[right]){
             left++;
         }
         else{
             right--;
         }
        
     }
     
     return maxArea;
    }
}