LeetCode. 11. Container With Most Water

Problem: Container With Most Water

Two pointers

For indices l < r, the two vertical lines hold water up to the shorter line. Their container has width r - l, height min(height[l], height[r]), and area

Start with the widest possible pair, the two ends of the array. Record its area, then move the pointer at the shorter line inward. If both heights are equal, move either one; this implementation moves the right pointer.

Why discarding the shorter side is safe

Suppose height[l] <= height[r]. The current area is bounded by height[l]. If we keep l and choose any narrower container with a right endpoint r' < r, its width is smaller than r-l, and its height is at most height[l] because the left wall is still height[l]. Thus its area cannot exceed the current area. No better answer can use l with a right endpoint inside r, so we can discard l and advance it. The symmetric argument applies when the right side is shorter. Repeating this leaves no potentially better pair unexamined.

Java implementation

The constraints are 2 <= height.length <= 10^5 and 0 <= height[i] <= 10^4. Therefore the largest possible area is at most (10^5 - 1) * 10^4 = 999,990,000, which fits in a signed 32-bit int; both the multiplication and the result can use int.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;

        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return best;
    }
}

Each pointer moves inward at most N times, so the algorithm takes O(N) time and uses O(1) extra space.