Module 04 · Two Pointers and In-Place Read/Write State

038. Container With Most Water

Interview · Download this solution · All solutions and shared helpers

Problem

Given nonnegative heights at unit-spaced indices, choose two distinct lines maximizing (right-left)*min(height[left],height[right]). Return that area; fewer than two lines return zero. Interior lines do not reduce the container's capacity.

Examples

Example 1

max_container([1, 8, 6, 2, 5, 4, 8, 3, 7])
=> 49

Indices one and eight give width seven and limiting height seven.

Example 2

max_container([])
=> 0

Two lines do not exist.

Example 3

max_container([2, 2])
=> 2

Width one times height two.

Reveal the worked solution and reasoning

Why this mechanism works

The shorter endpoint limits the current water height. Keeping it while narrowing the width cannot improve the area, even if the other line becomes taller. Therefore discard the shorter endpoint after recording the area. This is an elimination argument, not a claim that each next area increases.

State and boundaries

left and right are candidate endpoints. best is the maximum area evaluated before discarding a frontier.

Protocol

Evaluate area using width times the shorter height.
Update best.
Move the shorter endpoint inward.
Repeat while two endpoints remain.

Visualization

left height 1 ........ right height 7
capacity limited by 1
keep 1 + narrower width cannot improve

Python implementation

def max_container(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        area = (right - left) * min(heights[left], heights[right])
        best = max(best, area)
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

max_container([1, 8, 6, 2, 5, 4, 8, 3, 7])

L2 max_container: left, right = 0, len(heights) - 1
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=0; right=8

L3 max_container: best = 0
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=0; right=8; best=0

L5 max_container: area = (right - left) * min(heights[left], heights[right])
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=0; right=8; best=0; area=8

L6 max_container: best = max(best, area)
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=0; right=8; best=8; area=8

L8 max_container: left += 1
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=1; right=8; best=8; area=8

L5 max_container: area = (right - left) * min(heights[left], heights[right])
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=1; right=8; best=8; area=49

L6 max_container: best = max(best, area)
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=1; right=8; best=49; area=49

L10 max_container: right -= 1
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=1; right=7; best=49; area=49

... 8 intermediate state changes omitted ...

L5 max_container: area = (right - left) * min(heights[left], heights[right])
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=4; right=6; best=49; area=10

L8 max_container: left += 1
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=5; right=6; best=49; area=10

L5 max_container: area = (right - left) * min(heights[left], heights[right])
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=5; right=6; best=49; area=4

L8 max_container: left += 1
heights=[1, 8, 6, 2, 5, 4, 8, 3, ...]; left=6; right=6; best=49; area=4

Result: 49. Indices one and eight give width seven and limiting height seven.

max_container([])

L2 max_container: left, right = 0, len(heights) - 1
heights=[]; left=0; right=-1

L3 max_container: best = 0
heights=[]; left=0; right=-1; best=0

Result: 0. Two lines do not exist.

Why the solution is correct

Every pair using the discarded short endpoint with a narrower width has area no larger than the pair just checked. Hence discarding that endpoint cannot hide a better answer. Repeating this safe elimination eventually covers or dominates every pair.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Moving the taller endpoint has no elimination proof. Summing trapped water answers a different problem from choosing one container.

Reasoning card

State: left and right are candidate endpoints. best is the maximum area evaluated before discarding a frontier.

Invariant: Discarded shorter boundaries cannot form a better container.

Decision to rehearse: Move the shorter boundary because the taller one cannot compensate for it.

Finish: Repeat while two endpoints remain

Transfer exercise

Allow nonuniform x-coordinates and replace index distance by coordinate distance in both the formula and proof.