Container With Most Water

The hard part is not calculating width × shorter_height. It is proving why one whole family of pairs can be discarded without checking them.

Start with the area formula

For two distinct indices l < r, the lines form a container with:

• Width: r - l
• Usable height: min(height[l], height[r])
• Area: (r - l) * min(height[l], height[r])

The shorter line determines the water level. The taller line cannot compensate for a shorter boundary because the container cannot be slanted.

For the canonical input:

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

the maximum area is 49, formed by indices 1 and 8:

width = 8 - 1 = 7
height = min(8, 7) = 7
area = 7 * 7 = 49

A useful direction for the Container With Most Water solution is to begin with the widest possible pair, then move inward while preserving the possibility of finding a taller limiting boundary. The pointer movement needs a proof; otherwise, “move the shorter side” is only a memorized trick.

The input can contain up to 10^5 heights, so the number of candidate pairs is the first constraint to take seriously.

The brute-force baseline exposes the bottleneck

The obvious correct approach is to enumerate every pair (i, j) where i < j, calculate its area, and retain the largest result:

best = 0

for i from 0 to n - 1:
    for j from i + 1 to n - 1:
        width = j - i
        usable_height = min(height[i], height[j])
        best = max(best, width * usable_height)

return best

There are approximately n² / 2 pairs. The extra space is O(1), but the time complexity is O(n²).

This baseline is still valuable. It confirms the formula, gives you a simple reference implementation for tests, and reveals the actual bottleneck: repeated pair evaluation. For n = 10^5, checking pairs one by one is not a viable plan. We need to eliminate candidates in groups.

Be precise about width. The lines sit at coordinates i and j, so their distance is j - i, not j - i + 1. The number of array positions between two indices is a different measurement from the distance between the vertical boundaries.

Recognize the opposite-end two-pointer structure

Place one pointer at each end:

left = 0
right = n - 1

This is the widest possible container. Every later move makes the width smaller, which creates the central tradeoff:

• Moving inward decreases width.
• A better answer is possible only if the move finds enough height to compensate.

At each state:

1. Evaluate the current pair.
2. Record its area in best.
3. Move the pointer at the shorter boundary.

This is a two-pointer pattern, but not the sorted-array version used to adjust a sum. It is also not fast-and-slow pointers or a sliding window. The useful signal here is the bottleneck invariant:

The shorter boundary caps the area, and keeping that boundary while narrowing the interval cannot improve the result.

The array does not need to be sorted. The proof comes from the geometry of width and limiting height.

Why moving the shorter boundary is safe

Assume the current pointers are l and r, and:

height[l] <= height[r]

The current area is:

(r - l) * height[l]

Now consider every pair that keeps l but chooses a new right endpoint k with l < k < r. For each such pair:

• Its width is smaller: k - l < r - l.
• Its usable height is at most height[l], because height[l] is still one of the boundaries.

Therefore:

area(l, k)
= (k - l) * min(height[l], height[k])
<= (k - l) * height[l]
< (r - l) * height[l]
= area(l, r)

Every container that keeps the current left boundary and moves the right boundary inward is strictly worse than the current pair. We can discard those pairs together and advance left.

The other case is symmetric. If height[r] < height[l], every pair that keeps r and moves left inward has both smaller width and usable height no greater than height[r]. Those pairs cannot improve the current area, so we decrement right.

The shorter boundary is the bottleneck. Keeping a bottleneck while throwing away width is a losing trade.

Equal heights

If:

height[l] == height[r]

both boundaries are limiting, and moving either pointer is safe. For example, if we advance left, every pair (left, k) with k < right has smaller width and usable height at most height[left]. The symmetric argument works if we decrement right.

Use a deterministic rule:

if height[left] <= height[right]:
    left += 1
else:
    right -= 1

The <= sends equal-height cases to the left pointer. Moving the right pointer would also be correct; the important requirement is to move exactly one pointer.

The invariant

At every iteration, the current pair has been evaluated. After moving the shorter boundary, every pair eliminated by that move has area no greater than the current evaluated area. Therefore, the move cannot remove an unevaluated optimal pair.

That is the two pointer area proof. The algorithm does not inspect every pair. It proves which pairs cannot win, then removes them from consideration.

Translate the proof into Python

The implementation needs only three pieces of meaningful state:

• left identifies the left boundary.
• right identifies the right boundary.
• best stores the largest area found so far.

Keep the code close to the proof:

def max_area(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    best = 0

    while left < right:
        width = right - left
        limiting_height = min(height[left], height[right])
        current_area = width * limiting_height
        best = max(best, current_area)

        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1

    return best

The order matters: calculate the current pair, update best, then move one pointer. Do not move a pointer before evaluating the current pair. The outermost pair may be the answer, especially when there are only two lines or when the heights are equal.

Both pointers move only inward. Across the scan, each pointer advances or retreats at most n - 1 times, and each iteration performs constant work. The total time is therefore O(n), with O(1) auxiliary space.

Dry-run the decisive states

For:

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

these states show the mechanism:

left	right	Boundary heights	Width	Area	Movement	Best
0	8	1, 7	8	8	Move left	8
1	8	8, 7	7	49	Move right	49
1	7	8, 3	6	18	Move right	49
1	6	8, 8	5	40	Move left on equality	49
2	6	6, 8	4	24	Move left	49
3	6	2, 8	3	6	Move left	49
4	6	5, 8	2	10	Move left	49

The first pair is wide but shallow. The optimal pair is narrower but much taller. The algorithm does not assume the widest pair wins; it uses that pair as the only safe starting point, then spends width to search for a higher bottleneck.

Edge cases and failure modes

For [1, 1], the only pair has width 1, limiting height 1, and area 1. The equality rule moves one pointer and the loop ends.

For [2, 2, 2], the first pair has area 2 * 2 = 4. After one pointer moves, the remaining pair has width 1 and area 2, so the original result remains best.

For [0, 5], the result is 0. Zero is a valid height, so initialize best to 0 rather than assuming a positive answer.

Increasing and decreasing inputs are useful debugging cases. In an increasing array, the left side is initially shorter, so left moves. In a decreasing array, right moves. If the implementation moves the taller pointer, the proof has been inverted.

Common mistakes:

• Using right - left + 1: that counts positions rather than the distance between lines.
• Moving the taller pointer: the shorter side still caps the area, so narrowing around it cannot create a better candidate.
• Moving both pointers: the proof eliminates one boundary, not both; moving both can skip a candidate.
• Updating after moving: evaluate the current pair before discarding a boundary.
• Returning the last area: later pairs are narrower and may be worse. Return best.
• Ignoring equality: either pointer is safe, but one must still move.
• Allowing left == right as a pair: the loop condition left < right keeps the indices distinct.

Complexity and final checks

The optimized maximum water container algorithm uses:

• Time: O(n)
• Auxiliary space: O(1)

Before submitting, check the implementation against the proof:

• Is the area based on min(height[left], height[right])?
• Is the width exactly right - left?
• Is best updated on every iteration?
• Does exactly one pointer move?
• Does the shorter boundary move?
• Is equality handled consistently?
• Does the scan stop when left == right?
• Does the function return best?

The transferable reasoning move

When a pair objective starts with the widest possible interval and one boundary is the bottleneck, ask:

If I keep the bottleneck boundary and reduce the width, can any remaining candidate improve the score?

Here, the answer is no. That lets us discard the shorter boundary, preserve the possibility of an optimal pair, and let the pointers converge.

Do not memorize “move the shorter pointer” by itself. Re-derive the discarded family, state the invariant, and then write the smallest loop that makes the proof visible. That is the reusable signal for the next opposite-end two-pointer problem.