11. 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 and n is at least 2.

Solution:

The area of water is determined by the distance of two lines and the smaller number of the line.

We start from the leftmost line and rightmost line and use them to calculate the total water and choose it to be a candidate.

If there is a better pair which gives more water, the distance between the left and right line will be shorter. That is to say at least one height of the line has to be larger.

In this case, the smaller one of the left and right line cannot support a higher level of water. So we move the smaller line one step to the middle.



Code:

public class Solution {
    public int maxArea(int[] height) {
        
        int left = 0;
        int right = height.length - 1;
        int water = 0;
        
        while (left < right) {
            water = Math.max(water, getArea(height, left, right));
            if (height[left] < height[right]) {
                left++;
            }
            else {
                right--;
            }
        }
        
        return water;
    }
    
    public int getArea(int[] height, int left, int right) {
        return (right - left) * Math.min(height[left], height[right]);
    }
}