The O(n) Club: Container With Most Water—Why Your Pointers Keep Drowning

The O(n) Club: Container With Most Water—Why Your Pointers Keep Drowning

⚡ TL;DR

Find the maximum water held between two lines—so easy in brute force, your CPU will revolt. Two-pointer saves the day in O(n):

// Brute force—how to anger a silicon chip
int maxArea = 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);
        maxArea = Math.max(maxArea, area);
    }
}

🧠 How Devs Usually Mess This Up

Instead of letting the shorter line set the rules, you move the taller pointer, expecting a miracle. Spoiler: gravity and water, like interviewers, are ruthlessly consistent—they only care about the weakest side. Shuffling the tall side is like bringing a raincoat to a drought. Don’t do it.

🔍 What’s Actually Going On

Imagine building a dam: the lowest wall decides when Niagara Falls begins in your backyard. The area is always min(height[left], height[right]) × (right − left). Start wide and close in. Every step you move the shorter wall, you might find a surprise upgrade. Move the taller? You just made the container narrower for no reason. It’s “wine glass selection meets physics.”

🛠️ PseudoCode

• Initialize: left = 0, right = height.length - 1, maxArea = 0
• While left < right:
  • area = min(height[left], height[right]) × (right - left)
  • maxArea = Math.max(maxArea, area)
  • Move the pointer at the shorter line inward
• Done: When pointers meet, maxArea is your answer.

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• All heights zero? Even your for-loop gets existential. Output: zero.
• Only two lines? Congrats, you just made a leaky straw.
• Identical heights? Maximum area depends on distance, not dreams.
• Complexity: O(n) time, O(1) space. Fast enough for recruiters, light enough for your RAM.

🧠 Interviewer Brain-Tattoo

Don’t let the tall lines distract you. It’s always the shortest wall holding back the ocean—and probably your offer letter.