Container With Most Water

NeetCode: Container With Most Water · LeetCode: 11. Container With Most Water · Difficulty: Medium

Given heights of vertical lines at positions 0..n, choose two lines that, together with the x-axis, form a container holding the most water. Return that maximum area. The container can't be tilted.

Example

Text

Input:  height = [1, 7, 2, 5, 4, 7, 3, 6]    Output: 36    (lines at index 1 and 7: min(7, 6) x 6)
Input:  height = [2, 2, 2]                    Output: 4

Brute force: try every pair

The area for lines i < j is min(h[i], h[j]) * (j - i).

Java

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

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

Output

36
4

Time: O(n²). Space: O(1). The area is an int product, which wraps silently on overflow; use long if heights and widths can be large. The examples here are small.

Optimal: two pointers, move the shorter wall

Start with the widest container (both ends). The water level is limited by the shorter wall. Moving the taller wall inward can only shrink the width without ever raising the limit, so it can never help. Moving the shorter wall is the only move that might find a taller limit. Repeat until the pointers meet, remembering the best area.

Java

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int best = 0;
        while (left < right) {
            int width = right - left;
            best = Math.max(best, Math.min(height[left], height[right]) * width);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

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

Output

36
4

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