Container With Most Water — Greedy Two Pointers

Problem Statement#

Given an integer array height where each entry is the height of a vertical line at index i, find two lines that, together with the x-axis, form a container holding the most water. Return the maximum amount of water.

Constraints:

• 2 <= height.length <= 10^5
• 0 <= height[i] <= 10^4

Input:  height = [1,8,6,2,5,4,8,3,7]
Output: 49

Input:  height = [1,1]
Output: 1

Why This Problem Matters#

LeetCode 11 is a top-five most asked two-pointer problem at Google, Microsoft, Amazon, Meta, and Apple. It is a common phone screen because it has an obvious O(n^2) brute force and a clever O(n) two-pointer solution that hinges on a non-trivial greedy argument.

Interviewers love this problem because the optimal solution is short but the correctness proof is not. Candidates who can articulate why moving the shorter pointer is safe — and why moving the taller one cannot improve the answer — pass quickly. Candidates who only memorize the code often stumble on follow-up questions.

The same greedy reasoning powers LC 42 (Trapping Rain Water) and many problems on monotonic boundaries. Mastering it here pays dividends.

The Core Insight#

The water held between indices l and r is min(height[l], height[r]) * (r - l). Start with the widest possible container — pointers at the two ends — and move the shorter side inward.

Why does this work? Suppose height[l] <= height[r]. Any container that keeps l fixed and brings r inward strictly loses width and is bounded above by height[l], so it can never beat the current area. Therefore the only way to potentially improve is to move l inward. The same argument by symmetry holds when the right side is shorter.

This is a textbook example of a greedy two-pointer scan: O(n) time, no precomputation, no extra data structures.

Visual Dry Run#

Trace height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

Best is 49.

Solution (Optimal)#

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
 
        while left < right:
            h = min(height[left], height[right])
            best = max(best, h * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
 
        return best

var maxArea = function (height) {
    let left = 0;
    let right = height.length - 1;
    let best = 0;
 
    while (left < right) {
        const h = Math.min(height[left], height[right]);
        best = Math.max(best, h * (right - left));
        if (height[left] < height[right]) left++;
        else right--;
    }
 
    return best;
};

Time: O(n) — pointers converge in linear time. Space: O(1) — constant scalars.

Common Mistakes#

• Moving the taller pointer. The current container already maxes out at the shorter height; advancing the taller side cannot improve area.
• Computing height as max instead of min. The water is bounded by the shorter line.
• Brute forcing all pairs in O(n^2). Works for tiny inputs but TLEs for n = 10^5.
• Off-by-one on the width. It is right - left, not right - left + 1, because there are no walls at the indices themselves to count twice.
• Returning when both heights are equal. Either pointer can be moved; common convention is to move left for consistency.

Interview Tips#

• State and prove the greedy: "moving the shorter side inward is the only operation that can potentially increase the area."
• Walk through one full trace before coding.
• Use min / max rather than nested if-else for readability.
• Mention LC 42 as a closely related problem and how the same logic generalizes.
• Sanity-check on [1, 1] to confirm width-1 base case yields 1.

Follow-up Questions#

• Return the indices of the optimal pair. Hint: track bestLeft and bestRight when best updates.
• 3D version with rectangular containers. Hint: not solvable in O(n) — reduces to harder geometric problems.
• What if heights can be negative? Hint: model meaningless physically; redefine the problem.
• Streaming version. Hint: harder; the optimal pair can be far apart.
• LC 42 (Trapping Rain Water) — same array, different question. Hint: use two pointers tracking running max from each side.

Key Takeaways#

• LeetCode 11 finds the maximum-area container using two pointers.
• Greedy: always move the shorter pointer inward.
• Area at any state is min(height[l], height[r]) * (r - l).
• Time O(n), space O(1).
• Correctness rests on the proof that moving the taller pointer cannot improve area.
• The same greedy logic underpins LC 42 (Trapping Rain Water).
• One of the most-asked phone-screen problems at Google, Microsoft, Amazon, Meta, and Apple.