Container with most water

leetcode 11.

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Solution. This one has a greed solution which takes O(n) time and O(1) space. Set a left and right pointers to the pillars. Each time, calculate the area height[left] and height[right] can cover. Then, compare the height[left] and height[right], move the shorter pillar toward the center by 1 step.

Take a look at below example. Say we have pillars in both sides with height of h1 and h2.

From case1 and case2, we know, no matter what the right pillar will be, the area size(S2 or S3)will be always smaller than S1. This allow us to move the left pillar to right in order to find a larger size.

From case3 and case4, we know only when we move the pillar to another one which is taller than current pillar, then it would be possible to find a larger size.

My code on github.

public int maxArea(int[] height) {
    int max = 0, left = 0, right = height.length - 1;
    while (left < right) {
        int currArea = (right - left) * Math.min(height[right], height[left]);
        max = Math.max(max, currArea);
        if (height[left] < height[right]) { // move the shorter pillar inside
            left++;
        }
        else {
            right--;
        }
    }
    return max;
}