[Leetcode] Container With Most Water

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.
Note: You may not slant the container.

We only need to maintain two pointers from left end and right end, calculate the area indicated by this two pointers and then move the lower height. The only chance we could get a larger area is by moving the lower height since when we move left or right inward the length of the "rectangle" is decreasing. In this way, we could guarantee to meet the optimal solution. The prove is as follow:

• Suppose the optimal solution is indicated by index i and j. And at one time, one of the left and right pointer would first meet i or j. We assume that left first meet i. Since we only move the pointer with lower height. If some times we move i before right actually arrived at j. This means there is a higher position k that height[k] >= height[i] and (k - i) > (j - i), meaning we could get an even larger area. This contradict with our assumption. So this could not happend. So we guarantee that we would meet the optimal solution.

    public int maxArea(int[] height) {
        int n = height.length;
        if(n < 2)
            return 0; // corner case
        int left = 0, right = n - 1;
        int ma = Integer.MIN_VALUE;
        while(left < right) {
            int area = (right - left)*Math.min(height[left], height[right]);
            ma = Math.max(ma, area);
            if(height[left] < height[right]) // only move the lower height to try to find the larger area
                left++;
            else
                right--;
        }
        return ma;
    }