Container With Most Water

Given n non-negative heights, where line i goes from (i, 0) to (i, height[i]), find two lines that form a container with the x-axis holding the most water. Return that amount. n is at least 2.

The water between lines i < j is limited by the shorter line: area = (j - i) * min(height[i], height[j]).

LeetCode: 11. Container With Most Water

Example

Text

Input:  [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49   (lines 1 and 8: width 7, height min(8, 7) = 7)

Brute force: every pair

Java

public class Main {
    static int maxArea(int[] height) {
        int best = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
        System.out.println(maxArea(new int[]{1, 1}));
    }
}

Output

49
1

Time: O(n²). Space: O(1).

Optimal: two pointers, move the shorter line

Start with the widest container, i = 0 and j = n - 1. Suppose height[i] <= height[j]. Every other container that uses line i is narrower, and its height is still at most height[i], so none can beat the current one. Line i can be discarded: move i right. By the same argument, if height[j] is shorter, move j left. Each step discards one line, so the loop runs n - 1 times.

Java

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

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
        System.out.println(maxArea(new int[]{1, 1}));
        System.out.println(maxArea(new int[]{4, 3, 2, 1, 4}));
    }
}

Output

49
1
16

Time: O(n). Space: O(1).

Edge cases

Equal heights at both ends: moving either pointer is safe; neither line can form a larger container with anything in between.
Large inputs: width * height is an int multiplication and wraps silently past Integer.MAX_VALUE. Compute the area as (long) (j - i) * Math.min(...) and keep best as a long if the limits allow it.