Container With Most Water: Why You Move the Shorter Wall

Container with most water is the two-pointer problem where the code is five lines and the whole interview is about one sentence: why is it safe to move the shorter wall? Anyone can write the loop from memory. The candidates who stand out can explain, without hand-waving, why the loop never throws away the answer. This article builds that explanation, then checks it against a brute force.

The problem it solves

You get a row of non-negative wall heights. Pick two walls; the water they hold is the distance between them times the shorter of the two, because water spills over the lower side. Return the largest amount any pair can hold.

For [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49: the walls at index 1 (height 8) and index 8 (height 7) are 7 apart, and 7 × 7 = 49. The walls in between do not matter. They are not obstacles; only the two chosen walls count.

Trying every pair is O(n²): fine for a hundred walls, too slow for a hundred thousand. The two-pointer version finds the same answer in one pass.

The intuition

Start with the widest container: one pointer on the first wall, one on the last. Width can only shrink from here, so any better container has to be taller.

Now look at the shorter of the two walls, say the left one. Pair it with any wall strictly inside the current range. The width is smaller, and the height is at most the left wall's height, because the shorter wall still caps the water. So every container that uses this left wall with an inner partner is no better than the one you just measured. The left wall has nothing left to offer. Drop it and move the left pointer inward.

That is the whole proof. Each step discards one wall together with every pair it could still form, and each discarded pair was provably no larger than an area already recorded. After n - 1 steps every pair has been either measured or ruled out, so the best recorded area is the answer.

Two consequences are worth saying out loud:

• Moving the taller wall is wrong, not just slow. The shorter wall still caps every container it forms, so you would keep the limit and lose width.
• Ties do not matter. When both walls are equal, either one can go: any inner container that keeps one of them is capped by that same height and is narrower.

Watch it run

The animation uses the same heights, [1, 8, 6, 2, 5, 4, 8, 3, 7]. The first container is 8 wide and 1 tall, an area of 8, and the left wall is the short one, so it goes. Next, walls 8 and 7 are 7 apart: 7 × 7 = 49, a new best. From there the right wall is always the shorter one, so it keeps moving: 18, then 40, then 16, 15, 4 and 6, each still under 49. The last frame sums it up: every move dropped the short wall and every pair that wall could still form, one pass, O(n).

The code

The lesson's loop, extended to also return which pair of walls wins:

def max_area(height):
    left, right = 0, len(height) - 1
    best, pair = 0, None
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        if area > best:
            best, pair = area, (left, right)
        if height[left] < height[right]:
            left += 1                          # the shorter wall can only improve by moving
        else:
            right -= 1
    return best, pair

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))          # (49, (1, 8))
print(max_area([1, 1]), max_area([4, 3, 2, 1, 4]))    # (1, (0, 1)) (16, (0, 4))
print(max_area([5]))                                  # (0, None)

The tempting mistake, moving the taller wall instead, finds only the first container on the example:

def move_taller(height):
    left, right, best = 0, len(height) - 1, 0
    while left < right:
        best = max(best, min(height[left], height[right]) * (right - left))
        if height[left] > height[right]:
            left += 1                          # wrong: keeps the wall that limits the water
        else:
            right -= 1
    return best

print(move_taller([1, 8, 6, 2, 5, 4, 8, 3, 7]))       # 8

Both the area and the reported pair against a brute force over every pair, on 2,000 random rows:

import random

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

random.seed(17)
ok = True
for _ in range(2000):
    h = [random.randint(0, 12) for _ in range(random.randint(0, 14))]
    best, pair = max_area(h)
    ok &= best == brute(h)
    if pair:
        i, j = pair
        ok &= min(h[i], h[j]) * (j - i) == best
print(ok)                                             # True

The complexity

• Brute force: O(n²) time, O(1) space; there are n(n - 1) / 2 pairs.
• Two pointers: O(n) time, because each step moves one pointer one position and they meet after n - 1 steps. O(1) extra space.
• Sorting does not help. The positions are the widths, so sorting the heights destroys the information the problem is about.

Where it goes wrong

• Using the taller wall for the area. The water level is min, not max. The mistake overestimates every container.
• Moving the wrong pointer. Moving the taller wall can skip the answer, as the example shows.
• Off-by-one widths. The width is right - left, not right - left + 1: two adjacent walls hold one unit of width.
• Confusing it with trapping rain water. That problem sums the water above every bar, and inner bars matter. Here only two walls count and the bars between them are ignored.
• Empty or one-wall input. No pair exists, so the answer is 0; the while left < right guard already handles it.

When it shows up in interviews

It is a standard medium, usually asked right after an easy two-pointer warm-up such as reversing an array or checking a palindrome. The code is rarely what separates candidates; the follow-up "why is moving the shorter wall safe?" is. Expect to be asked for the complexity, what happens with equal heights, and how it differs from trapping rain water. The same "discard the side that cannot improve" argument returns in two sum on a sorted array and in the staircase search on a sorted matrix.

How to say it in an interview

"I start with the widest container, one pointer at each end. The water is the width times the shorter wall. The shorter wall is the limit: any container that keeps it and moves the other pointer inward is narrower and no taller, so it cannot beat what I just measured. So I record the area and move the shorter wall inward. Every step rules out one wall and all its remaining pairs, so after one pass I have seen the best. That is O(n) time and O(1) space."

The general pattern is in two pointers explained, and the same elimination argument drives search in a 2D matrix.