Container With Most Water — Two-Pointer Walkthrough

Container With Most Water is 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).

Intuition

The brute force checks every pair: O(n^2). Dead on arrival for n up to 10^5.

The two-pointer trick: start with one pointer at each end. This maximizes the width. Compute the area, then move the pointer at the shorter line inward. Repeat until they meet.

Why is moving the shorter pointer the safe choice? Suppose height[left] < height[right]. Any container that keeps left fixed and moves right inward 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. The same argument applies symmetrically when right is shorter. When they tie, either move is safe.

This is the rare problem where the proof is short, the code is even shorter, and the result is O(n).

Explanation with 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.

idx :   0   1   2   3   4   5   6   7   8
hgt :   1   8   6   2   5   4   8   3   7

8       #               #
7       #               #           #
6       #   #           #           #
5       #   #       #   #           #
4       #   #       #   #           #
3       #   #       #   #       #   #
2       #   #   #   #   #       #   #
1   #   #   #   #   #   #       #   #

best pair: L=1 (h=8)  ->  R=8 (h=7)
area = min(8,7) * (8-1) = 7 * 7 = 49

L                                                  R
[1, 8, 6, 2, 5, 4, 8, 3, 7]     min=1  area= 1*8 = 8

 L                                               R
[1, 8, 6, 2, 5, 4, 8, 3, 7]     min=7  area= 7*7 = 49  BEST

 L                                          R
... continue inward, no area beats 49 ...

invariant: shrinking the shorter side
         cannot decrease the maximum we missed.

Code

def maxArea(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

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

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = (int)height.size() - 1, best = 0;
        while (left < right) {
            int h = min(height[left], height[right]);
            best = max(best, h * (right - left));
            if (height[left] < height[right]) left++;
            else right--;
        }
        return best;
    }
};

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.
• 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.
• State the complexity and stop.

Related Problems

• Trapping Rain Water
• 3Sum
• Two Sum II Input Array Is Sorted
• Squares of a Sorted Array

The general pattern is detailed in two pointers technique.

Wrap up

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.