Leetcode - Container With Most Water Solution

Finding the container with the most water starts with a brute force search over every pair. The two pointer version keeps the same result in O(n) time by discarding pairs that cannot improve the area.

The area constraint

The input height contains vertical lines. Line i runs from (i, 0) to (i, height[i]). For two indices left and right, the container width is right - left, and its height is min(height[left], height[right]). The area is their product.

My initial approach checked every possible pair of lines:

function maxAreaNaive(height) {
    let maxArea = 0;

    // Check every possible pair
    for (let i = 0; i < height.length - 1; i++) {
        for (let j = i + 1; j < height.length; j++) {
            let width = j - i;
            let currentArea = Math.min(height[i], height[j]) * width;
            maxArea = Math.max(maxArea, currentArea);
        }
    }

    return maxArea;
}

The pairwise method is correct, but it takes O(n²) time. With n up to 10^5, that many pair checks are too expensive.

Two pointer rule and implementation

Start with the first and last lines, which gives the widest possible container. If height[left] is shorter, moving right would reduce the width while leaving the limiting height unchanged or lower. That move cannot produce a better area for the current left line. Moving left is the only move that might find a taller limiting line. The same argument applies when the right line is shorter.

function maxArea(height) {
    let maxArea = 0;
    let start = 0;                    // Left pointer
    let end = height.length - 1;      // Right pointer

    while (start < end) {
        let width = end - start;
        // Area is limited by the shorter line
        let currentArea = Math.min(height[start], height[end]) * width;
        maxArea = Math.max(maxArea, currentArea);

        // Move the pointer with the shorter line
        if (height[start] <= height[end]) {
            start++;
        } else {
            end--;
        }
    }

    return maxArea;
}

// Driver Code
function main() {
    let heightsArray = [1, 8, 6, 2, 5, 4, 8, 3, 7];
    console.log("Input heights: ", heightsArray);
    let result = maxArea(heightsArray);
    console.log("Max water that can be contained: ", result);
}

main();

Invariant and trace

Each iteration evaluates the best area for the current pair, then removes the side that limits that area. For each discarded pair, the width is no larger than the current width. Its height is also no larger than the shorter line. Thus, its area cannot exceed the area already checked for that side.

For [1, 8, 6, 2, 5, 4, 8, 3, 7], the first three evaluations are:

• Start: left=0 (height=1), right=8 (height=7), area = min(1,7) × 8 = 8
• Move left (shorter): left=1 (height=8), right=8 (height=7), area = min(8,7) × 7 = 49
• Move right (shorter): left=1 (height=8), right=7 (height=3), area = min(8,3) × 6 = 18
• Continue until the pointers meet.

The maximum area found is 49.

Java implementation

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int start = 0;
        int end = height.length - 1;

        while (start < end) {
            int width = end - start;
            maxArea = Math.max(maxArea, Math.min(height[start], height[end]) * width);

            if (height[start] <= height[end]) {
                start++;
            } else {
                end--;
            }
        }

        return maxArea;
    }
}

Complexity and reusable rule

I did not expect this greedy rule to be sufficient. The scan takes O(n) time and uses O(1) extra space.

The useful pattern is to begin with the widest candidates and move the pointer that limits the current result. That rule is the reason this problem avoids the pairwise search.