LeetCode 11 Container With Most Water: Why the Two-Pointer Trick Is Correct

LeetCode 11, Container With Most Water, is one of the shortest solutions in the Blind 75 and one of the most commonly memorised without understanding. The loop is six lines. The interesting part is the one sentence most candidates cannot say when an interviewer asks, "How do you know you didn't skip the best pair?" This post answers that sentence properly, then covers code in three languages, edge cases, and the comparison with Trapping Rain Water that interviewers love to throw in as a follow-up.

The Problem: What LeetCode 11 Actually Asks

You are given an integer array height of length n. Each value is a vertical line drawn at x-coordinate i, from (i, 0) to (i, height[i]). Choose two lines that, together with the x-axis, form a container. Return the maximum amount of water the container can hold. You may not slant the container.

Constraints on LeetCode: 2 <= n <= 10^5 and 0 <= height[i] <= 10^4. That upper bound on n is the hint: an O(n²) solution performs around 5 billion pair checks in the worst case and will time out. You need O(n) or O(n log n).

The water held by lines i < j is a rectangle:

area(i, j) = min(height[i], height[j]) * (j - i)

Two details trip people up. First, the shorter line decides the water level, because water would spill over it. Second, the lines in between are irrelevant. They are infinitely thin and do not displace water or block it. If you start thinking about bars between the two lines, you are solving a different problem (we will come back to this).

Example: height = [1,8,6,2,5,4,8,3,7]. The best pair is index 1 (height 8) and index 8 (height 7): min(8,7) * (8-1) = 7 * 7 = 49.

Brute Force: Check Every Pair in O(n²)

The honest starting point in an interview is the brute force. State it, give its complexity, and move on. It also doubles as a test oracle when you want to verify the fast version.

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

That is n(n−1)/2 pairs. For n = 10⁵ that is roughly 5 × 10⁹ operations. Too slow. The question becomes: which pairs can we skip without ever examining them, and how do we prove that skipping them is safe?

The Key Insight: Width Only Shrinks, So Only Height Can Save You

Start with the widest possible container, i = 0 and j = n - 1. Any other pair has strictly less width. So for any other pair to win, it must have a strictly taller limiting line.

Now suppose height[i] < height[j]. Consider every pair that still uses line i with some partner k where i < k < j:

• Width: k - i < j - i. Strictly narrower.
• Height: min(height[i], height[k]) <= height[i]. Never taller than line i, no matter how tall k is.

So every one of those pairs has area at most height[i] * (k - i), which is less than height[i] * (j - i), which is exactly the area we just computed for (i, j). Line i has nothing better to offer. We discard it by doing i++.

Notice what we did not say. We did not say "moving the taller pointer is bad because the area will decrease". It might not decrease. The argument is about the shorter line: the shorter line has already achieved its best possible container, because it is paired with the farthest line it could ever be paired with among the remaining candidates.

Why moving the taller pointer would be wrong

If you moved the taller line j inward instead, you would discard line j without having proven anything about it. Line j might pair with some taller line k later to beat the current answer. Example: [1, 100, 100, 2]. Start at (0, 3): area min(1,2)*3 = 3. If you wrongly move the taller pointer (j at height 2) you get (0, 2) = 2, then (0, 1) = 1, and you never test (1, 2) = 100. Moving the shorter pointer correctly goes (1, 3) = 4, then (1, 2) = 100.

A Rigorous Proof That the Two-Pointer Greedy Never Skips the Answer

The intuition above is enough for most interviews. If you want to be bulletproof, or if the interviewer pushes ("prove it formally"), use the search-space elimination argument. It is the same style of proof used for Two Sum II on a sorted array, and it generalises to many two-pointer problems.

The search space as an upper triangle

Draw an n × n grid where cell (i, j) holds area(i, j). Only cells with i < j matter, so the search space is the upper triangle above the diagonal. Brute force visits every cell.

At any point, the remaining candidates are all pairs (a, b) with i <= a < b <= j. That is a triangle whose top-right corner is (i, j).

The invariant

Invariant: before each iteration, either the optimal pair lies inside the current window [i, j], or best already holds the optimal area.

1. Initialisation. At the start the window is the whole array, so the optimal pair is inside it. The invariant holds.
2. Maintenance, case h[i] < h[j]. We record area(i, j) into best, then remove row i, meaning all pairs (i, k) with i < k <= j. For k = j we just recorded it. For k < j, area(i, k) = min(h[i], h[k]) * (k - i) <= h[i] * (k - i) < h[i] * (j - i) = area(i, j) <= best. So every removed pair is at most best. If the optimum was among them, best already equals it. Otherwise it is still inside the smaller window.
3. Maintenance, case h[i] > h[j]. Symmetric: remove column j. Every pair (k, j) with i <= k < j has area at most h[j] * (j - k) <= h[j] * (j - i) = area(i, j).
4. Maintenance, case h[i] == h[j]. Both arguments apply, so you may remove either row or column. (You can even remove both, since any pair using either line is capped by that common height with less width.)
5. Termination. When i == j the window contains no pairs. By the invariant, best holds the optimum.

Each step removes at least one row or column, so there are at most n − 1 steps. That is where O(n) comes from. The brute force examines O(n²) cells; we examine one cell per row or column deleted and prove the rest of that row or column is dominated.

Dry Run on [1,8,6,2,5,4,8,3,7]

Indices 0 to 8. Watch the pointer at the shorter line move each time.

Eight area computations instead of 36. The answer 49 was found at step 2, and the proof guarantees the remaining six steps could not beat it without examining every skipped pair.

Look at step 1 through the proof lens. Line 0 has height 1. Its best possible container is with the farthest line, index 8, giving width 8 and area 8. Every other partner of line 0 gives at most 1 * (k - 0) < 8. So row 0 (eight pairs) is gone after one computation.

Code: Container With Most Water in C++, Java and Python

#include <vector>
#include <algorithm>
using namespace std;

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

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

from typing import List

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

Overflow check: the maximum area is 10^4 * (10^5 - 1), just under 10⁹, which fits in a 32-bit signed int (max about 2.147 × 10⁹). If an interviewer changes constraints to heights up to 10⁹, switch to long long / long. Mentioning this unprompted is a small but real signal.

An optimisation that keeps O(n) but skips useless lines

After moving past the shorter line, any new line that is not taller than the old limiting height cannot help: width shrank and height did not grow. You can skip such lines without computing their area.

def max_area_skip(height):
    i, j = 0, len(height) - 1
    best = 0
    while i < j:
        h = min(height[i], height[j])
        best = max(best, h * (j - i))
        # skip every line on either side that is not taller than h
        while i < j and height[i] <= h:
            i += 1
        while i < j and height[j] <= h:
            j -= 1
    return best

This is still O(n) worst case, and it often does fewer area computations. Note that it moves both pointers past any line at most h, which is exactly the "equal heights, move both" case from the proof. Present it as an optional refinement, not as your first answer. Interviewers want the clean version first.

Edge Cases and Common Bugs

Bugs I see repeatedly in mock interviews:

• Using j - i + 1 as width. Width is the distance between x-coordinates, j - i. For [1,1] the answer is 1, not 2.
• Using max instead of min for height. Water spills over the shorter side.
• Loop condition i <= j. When i == j the width is 0, harmless, but it shows you have not thought about what a pair is. Use i < j.
• Moving both pointers every step. That skips pairs and is wrong in general (it is only safe when heights are equal).
• Sorting the array. Indices are positions; sorting destroys the width information.

Test it against the brute force

Before trusting any greedy, run it against the brute force on random small arrays. This takes thirty seconds to write and it is how you would catch a "move the taller pointer" mistake on your own.

import random

def check(trials=2000):
    for _ in range(trials):
        n = random.randint(2, 9)
        h = [random.randint(0, 10) for _ in range(n)]
        assert Solution().maxArea(h) == max_area_brute(h), h
        assert max_area_skip(h) == max_area_brute(h), h
    print("all good")

Container With Most Water vs Trapping Rain Water

These two problems look almost identical in their diagrams, both use two pointers, and both have "water" in the title. They are different problems, and confusing them is one of the most common mistakes in interviews. Interviewers sometimes ask one as a follow-up to the other precisely to see whether you notice.

For the second problem with the same array: trapped water is computed per index. At index 3 (height 2) the max to the left is 8 and the max to the right is 8, so 6 units sit on top of it. Summing across all indices gives 2 + 6 + 3 + 4 + 4 = 19. That is nothing like 49, because Trapping Rain Water does not let you "pick" lines; the terrain is fixed and water fills every dip.

The two-pointer reasoning also differs in a subtle way. In Trapping Rain Water, you move the side whose running maximum is smaller, because that maximum is guaranteed to be the binding constraint for the current cell. In Container With Most Water, you move the side whose current line is shorter, because that line has exhausted its potential. The full walkthrough is in LeetCode 42 Trapping Rain Water explained.

How to Present It in the Interview

Because this problem is famous, many interviewers assume you have seen it. What separates a "hire" from a "lean hire" here is not the code. It is the clarity of your reasoning and how you handle the follow-ups. A good 10-minute flow looks like this:

1. Restate and pin the formula (1 minute). "Area is the shorter height times the index distance; lines in between don't matter, right?" Confirm with the interviewer.
2. Brute force (1 minute). "Check every pair, O(n²). With n up to 10⁵ that's about 5 billion pairs, too slow."
3. Insight (2 minutes). "Start widest. Any other pair is narrower, so it needs a taller limiting line. The shorter of the two current lines can't do better with any inner partner, so I drop it."
4. Code (2 minutes). Write the clean loop. Talk while you write.
5. Dry run (2 minutes). Use a small case like [1,100,100,2] that would break the wrong rule.
6. Complexity and edge cases (1 minute). O(n), O(1), equal heights, overflow on larger constraints.

If you struggle to narrate while coding, practise the technique in thinking out loud in coding interviews. For a general approach to unfamiliar problems, see how to approach a DSA problem in a coding interview.

Follow-up questions interviewers actually ask

• "What if heights are equal, which pointer do you move?" Either, or both. Explain why using the proof: both lines are capped at that height, and every inner pair using either is narrower.
• "Prove it." Use the row/column elimination argument. Mention the invariant explicitly.
• "Return the indices, not the area." Track bestI, bestJ whenever you update best. Ask what to return on ties.
• "What if the container can have a minimum width k?" The same loop works; stop when j - i < k. Pairs with smaller width are invalid and the elimination argument still holds within valid pairs.
• "What if lines have thickness?" This is a requirement change; restate the area formula with the interviewer before coding anything.
• "How is this different from Trapping Rain Water?" See the table above. Max of one pair versus sum over all positions.

Red flags

• Writing the solution instantly without any explanation. It signals memorisation, and the interviewer will dig until something breaks.
• Justifying the pointer move with "because the area decreases otherwise". That is false; the area can go up or down.
• Not testing an input where the wrong pointer choice fails.

Similar Problems to Practise Next

Once the elimination proof clicks, these problems will feel like variations on one idea.

Largest Rectangle in Histogram deserves a special mention. It sounds like a cousin of Container With Most Water, but because every bar between the two ends must be at least the rectangle's height, the two-pointer elimination no longer holds. That problem needs a monotonic stack, covered in stack, queue and monotonic stack problems. Recognising when a pattern stops applying is exactly the kind of judgment strong interviewers look for.

For a structured list that includes this problem and its siblings, compare the sheets in Blind 75 vs NeetCode 150 vs Striver SDE Sheet, and work through the array fundamentals in array interview problems and patterns.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.