Skip to content
../writing

Container With Most Water

Naseebullah AhmadiSenior Software Engineer, London

Pick two walls from a row so the water between them is as large as possible. Checking every pair works, but one observation about the shorter wall makes it a single pass.

#arrays
#two-pointers
#greedy
#interviews
7 min read
#algorithms

Each number is the height of a wall. Pick two walls, and the water they hold is the gap between them times the shorter wall, because water spills over the lower side.

@itsnas the-best-container.svg
The best containerNine walls with heights 1, 8, 6, 2, 5, 4, 8, 3, 7. The best pair is index 1 (height 8) and index 8 (height 7): width 7 times height 7 holds 49.1862548370369012345678IndexHeight
The best pair is walls 1 and 8: width 7, capped by the shorter wall at 7, so 49 units.

There are 36 pairs here. Checking them all is O(n2)O(n^2); this post gets there in 8 steps.

Start wide, then drop the shorter wall

Start with the widest container you can: the two end walls.

@itsnas the-first-container.svg
The first containerThe two end walls, index 0 with height 1 and index 8 with height 7, hold a container of width 8 and height 1, so 8 units.1862548370369012345678IndexHeight
Walls 0 and 8: width 8, but capped at height 1. Area 8.

It holds 8, capped by wall 0 at height 1. Now ask: could wall 0 be part of a better container? Any other partner sits closer to it, so the width shrinks, and the height can never go above 1 because wall 0 is still the shorter side. Every container that uses wall 0 is worse than this one. Wall 0 is finished, so move the left pointer in.

The same argument works at every step: the shorter wall has already had its best container, so drop it. Moving the taller wall instead can only shrink the width while the cap stays put, which is the one bug this problem has.

L (height)R (height)AreaMove
0 (1)8 (7)8 × 1 = 8left is shorter
1 (8)8 (7)7 × 7 = 49right is shorter, best
1 (8)7 (3)6 × 3 = 18right
1 (8)6 (8)5 × 8 = 40equal, either is safe
1 (8)5 (4)4 × 4 = 16right
1 (8)4 (5)3 × 5 = 15right
1 (8)3 (2)2 × 2 = 4right
1 (8)2 (6)1 × 6 = 6pointers meet

When the walls are equal, both are capped at the same height and anything narrower can't beat it, so moving either one is safe.

Record, then drop the shorter wall

Record the area first, then move: moving first skips a container.

@itsnas max-area.ts
codemax-area.ts
function maxArea(height: number[]): number {
  let left = 0
  let right = height.length - 1
  let best = 0
 
  while (left < right) {
    const width = right - left
    const shorter = Math.min(height[left], height[right])
    best = Math.max(best, width * shorter)
 
    if (height[left] < height[right]) left++ // shorter wall moves
    else right--
  }
 
  return best
}
main
Nas (@itsnas)

O(n)O(n) time, since each wall is dropped once, and O(1)O(1) space.

This is the same move as Two Sum II: start at the ends, and let one comparison prove a side can never help. Don't confuse it with Trapping Rain Water, which sums the water above every bar and needs the running maximum from each side, not just the best pair.

Container With Most WaterMedium
Two Sum II - Input Array Is SortedMedium
Trapping Rain WaterHard
Related patterns
Two Pointers