LeetCode Container With Most Water: Two-Pointer Walkthrough

Container With Most Water is LeetCode problem 11, rated Medium. It is the cleanest demonstration of the two-pointer technique that exists in the easy-to-medium tier, and the correctness argument is genuinely satisfying.

The Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are at (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container holds the most water. Return the maximum amount of water it can store.

The container is not slanted; the water level is bounded by the shorter wall.

Example:

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: Lines at index 1 and 8 form a container with area min(8, 7) * (8 - 1) = 49.

Area for indices i and j is min(height[i], height[j]) * (j - i).

Brute Force

Check every pair.

def max_area(height):
    best = 0
    n = len(height)
    for i in range(n):
        for j in range(i + 1, n):
            area = min(height[i], height[j]) * (j - i)
            best = max(best, area)
    return best

Time: O(n^2). Space: O(1). For n = 10^5 this is dead on arrival.

Optimal Solution

Use two pointers, one at each end. At every step we have a candidate area. We then move the pointer at the shorter line inward. The intuition: moving the taller pointer cannot help because the area is bounded by the shorter one, and the width is strictly decreasing.

def max_area(height):
    left = 0
    right = 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

Line by line:

• Initialize left and right at the two ends. This maximizes the width.
• Compute the bounded height as the min of the two walls.
• Compute and update best.
• Move the shorter pointer inward. If both walls are equal, moving either is safe; the code moves the right one.

Why is moving the shorter pointer safe? Suppose height[left] < height[right]. Any container that keeps left fixed and moves right further left has width strictly less than the current width and height bounded by height[left] or less. So its area cannot exceed the current. We can discard all those pairs and only consider moving left.

Walk Through an Example

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

• left = 0, right = 8. h = min(1, 7) = 1. area = 1 * 8 = 8. best = 8. Move left (1 < 7).
• left = 1, right = 8. h = min(8, 7) = 7. area = 7 * 7 = 49. best = 49. Move right (8 >= 7).
• left = 1, right = 7. h = min(8, 3) = 3. area = 3 * 6 = 18. Move right.
• left = 1, right = 6. h = min(8, 8) = 8. area = 8 * 5 = 40. Move right.
• left = 1, right = 5. h = min(8, 4) = 4. area = 4 * 4 = 16. Move right.
• left = 1, right = 4. h = min(8, 5) = 5. area = 5 * 3 = 15. Move right.
• left = 1, right = 3. h = min(8, 2) = 2. area = 2 * 2 = 4. Move right.
• left = 1, right = 2. h = min(8, 6) = 6. area = 6 * 1 = 6. Move right.
• left = 1, right = 1. Loop ends.

Return 49.

Edge Cases

• Length 2 array. The loop runs once and returns the only possible area.
• All equal heights like [5, 5, 5, 5]. The maximum area is 5 * (n - 1) and is found at the very first comparison.
• Strictly decreasing or strictly increasing heights. The two-pointer sweep still finds the optimum because the correctness proof does not depend on monotonicity.
• Zero heights. Area can be zero; algorithm handles it cleanly.

Complexity Analysis

• Time: O(n). Each iteration moves a pointer inward and the pointers meet after n - 1 steps.
• Space: O(1). Just two indices and a running max.

How to Explain It in an Interview

• Restate the problem and draw it. The picture is what sells the two-pointer intuition.
• Mention the brute force at O(n^2) and dismiss it.
• Explain the two-pointer setup: start wide, the width can only shrink, so we need to find a height jump that more than compensates.
• Argue why moving the shorter pointer is the safe choice. This is the bit the interviewer wants to hear.
• Code it. Mention the tie case explicitly so the interviewer knows you thought about it.
• State the complexity and stop.

Related Problems

• LeetCode 42 Trapping Rain Water
• LeetCode 15 3Sum
• LeetCode 167 Two Sum II Input Array Is Sorted
• LeetCode 977 Squares of a Sorted Array
• LeetCode 26 Remove Duplicates from Sorted Array

The general pattern is detailed in two pointers technique.

Wrap up

This problem is the cleanest possible example of “shrink the search space by an argument, not by brute trying.” The correctness proof is short, the code is shorter, and it is the gateway to a whole family of two-pointer problems. If you can deliver this with the proof intact, you have earned the medium rating.