Leetcode - Container With Most Water Solution

Finding the container that holds the most water looked like it would need nested loops at first. But there's an elegant two-pointer solution that runs in O(n) instead of O(n²). The key insight is to always move the pointer pointing to the shorter line, because that's the limiting factor for the area.

Starting with the widest possible container (first and last lines), we narrow it down by moving the shorter pointer inward. This greedy approach actually finds the optimal solution because we're always moving away from the limiting factor.

The Problem

I'm given an array height of length n, representing n vertical lines. The endpoints of line i are at (i, 0) and (i, height[i]). I need to find two lines that together with the x-axis form a container that holds the most water.

The area is calculated as: width × min(height[left], height[right])

My First Attempt

My initial approach was brute force. Check 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;
}

This worked, but it was O(n²). I knew there had to be a better way, especially since the constraints said n could be up to 10^5.

The Insight

I started thinking: "What if I start with the widest possible container (first and last lines) and then narrow it down?" But which pointer should I move?

The key insight: I should always move the pointer pointing to the shorter line. Why? Because:

• The area is limited by the shorter line
• Moving the shorter pointer might find a taller line, increasing the area
• Moving the taller pointer can only decrease the area (width decreases, height can't increase)

This was my "aha" moment!

The Two Pointers Solution

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();

Why This Works

The algorithm works because:

1. We start with maximum width
2. At each step, we move the shorter pointer inward
3. We're guaranteed not to miss the optimal solution because we're always moving away from the limiting factor (the shorter line)

Tracing Through an Example

Let me trace through [1, 8, 6, 2, 5, 4, 8, 3, 7]:

• 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 pointers meet...

The maximum area found is 49.

Java Version

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;
    }
}

What Surprised Me

I was surprised that this greedy approach actually finds the optimal solution. Usually, greedy algorithms can miss optimal solutions, but in this case, the logic of always moving the shorter pointer guarantees we don't miss anything.

Key Takeaways

• Two pointers technique can reduce O(n²) to O(n)
• Always move the pointer that's limiting the solution
• Starting from the extremes (widest container) is often a good strategy
• This pattern appears in many array problems

This problem really helped me understand when and how to use two pointers. It's become one of my go-to techniques for array problems!