Container With Most Water

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

Algorithm:
1. The problem is to find out the largest area that it can create with left and right and axis of y=0.
2. The area = Min height of either side * the distance
3. Maintain the max and reduce the left and right pointer on both side.
*/
public class Solution {
    public int maxArea(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while(right > left) {
            int cur = Math.min(height[left], height[right]) * (right - left);
            if(cur > max) {
                max = cur;
            }
            if(height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return max;
    }
}