LeetCode (Algorithms#11) ‒ Container With Most Water

Problem

Given n non-negative integers a1, a2, ..., an, 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, 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

To clarify the problem, we are searching for the coordinates a_i and a_j for j>i, 0<i,j<n such that the area (j-i)*min(a_i,a_j) is maximized. The bruteforce solution is clearly O(n^2), and the problem cannot benefit from being sorted (since the solution depends on the original ordering). The trick to finding the optimal solution, which runs in O(n), is to recognize that as you reduce the width of the container by one, then either the lower height must increase, or both height must increase by one or more to have a larger area. Thus, starting with a_0 and a_n, yielding the widest container, we can iterate on the side with the shorter height while maintaining the maximum area. If a larger container does exist, the height will have to be larger to make up for the smaller width, and so the side with the smaller height will iterate towards it. Trying a few examples can convince yourself that this is correct.

Time complexity: O(n)
Space complexity: O(n)
Runtime: 10 ms (63.17%)

1 2 3 4 5 6 7 8 9 10 11 12

public int maxArea(int[] height) { int i=0, j=height.length-1, area=0; while (i<j) { area = Math.max(area, (j-i)*Math.min(height[i],height[j])); if (height[i] > height[j]) { j--; } else { i++; } } return area; }