← DSA Atlas
Dedicated problem page · #11

Container With Most Water

MediumTwo PointersConverging pointers on a width-vs-height tradeoffTwo pointers (greedy)
Solve on LeetCode ↗
11
MediumTwo PointersTwo pointers (greedy)Converging pointers on a width-vs-height tradeoff

Container With Most Water

Given an array height where height[i] is the height of a vertical line at position i, pick two lines that together with the x-axis form a container holding the most water. Return that maximum area, where area = (distance between the two lines) * min(height of the two lines).

Open official problem prompt ↗
In plain English

Find the two vertical lines that trap the greatest volume of water between them.

Picture it like this

Two people hold the ends of a flexible trough as wide as the array; water spills over the shorter side, so the shorter holder steps inward hoping to find a taller wall worth the lost width.

Example
Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output
49
Why
Lines at indices 1 and 8 (heights 8 and 7) give width 7 * min(8,7) = 7 * 7 = 49, the largest possible.
Constraints
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
Pattern lesson

See the pattern, then code

Converging pointers on a width-vs-height tradeoff
Recognition clue

You want the best pair over all index pairs where value depends on the gap between them and the smaller of two endpoints, which screams two pointers starting at the widest gap.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Start at the maximum possible width and always move the pointer at the shorter line inward, since keeping the shorter line can never beat what we just measured while width only shrinks.

New words, made simpleKnow these before the algorithm
Width
The horizontal distance right - left between the two chosen lines.
Binding height
The shorter of the two endpoint heights, which caps how high the water can rise.
Greedy move
Advancing the shorter side because it is the only side that could improve the area.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
All pairs

Quadratic time times out for n up to 100000.

Compute the area for every pair (i, j) and keep the maximum.

Time O(n^2)Space O(1)
Best choiceConverging two pointers

Linear and optimal; each step provably cannot skip a better answer.

Start wide and always discard the shorter wall, shrinking width but chasing taller walls.

Time O(n)Space O(1)
The rule we keep true

Invariant

The best area achievable using any pair still inside the current [left, right] window is never lost by moving the shorter pointer inward.

Why this is correct

Reasoning

The area is limited by the shorter wall. Any other container using that shorter wall would have less width than the one just measured, so it cannot be larger; discarding the shorter wall therefore throws away only options that are already dominated.

The algorithm in three movesSay these aloud before coding
1Place left at 0 and right at n-1 to start with maximal width

left=0,right=8 -> 8*min(1,7)=8

2Compute the area as width times the shorter of the two heights and update the best

left=1,right=8 -> 7*min(8,7)=49

3Move the pointer at the shorter line inward

best = 49

4Repeat until the pointers meet

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
81
62
23
54
45
86
37
78
1 · Readleft=0(1), right=8(7)
2 · AskArea here?
3 · Update state8 * min(1,7) = 8
4 · Resultbest=8; left wall shorter, move left.
Key takeaway

The lines of height 8 (index 1) and 7 (index 8) bound the widest tall container, area 49.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Widest start

    Beginning at the extremes guarantees the maximum width is considered first.

  2. 2
    Lines 6-7Measure area

    Width times the binding (shorter) height, updating the running best.

  3. 3
    Lines 8-11Move the shorter side

    Only advancing the shorter wall can possibly increase the min height enough to offset lost width.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Exactly two lines returns their single container area
  • All equal heights: answer is (n-1) * that height
  • A zero-height line contributes zero area but is still a valid endpoint
!

Common beginner mistakes

  • Moving the taller pointer, which can skip the true optimum
  • Multiplying by max height instead of min height
  • Using n instead of right-left for width
Check your understanding

When both walls are equal height, does it matter which pointer we move?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima#75Sort ColorsDutch National Flag partition