Container With Most Water

Pick two heights that hold the most water.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Container With Most Water: Evaluate both boundary walls, then move only the shorter wall because keeping it cannot produce a taller container at a smaller width.

Input and goalPick two heights that hold the most water.

Initialize at both endsFor heights [1, 8, 6, 2, 5, 4, 8, 3, 7], L=0 and R=8 give width 8 and area 8. Height 1 is limiting, so move L right.

8 x min(1, 7) = 8

L=1081622354458637R=78

coveredRange[0..8]bestmax(0, 8) = 8moveL: 0 -> 1reasonleft height 1 < right height 7

Recognize it

Choose two boundary positions to maximize width times the smaller boundary height; moving inward always loses width, so only a taller limiting wall can compensate.

Keep true

Before each iteration, best is the largest area among discarded boundary pairs. Moving the shorter wall cannot discard a better pair because every pair that keeps it has smaller width and height no greater than that same short wall.

Reuse it

When moving either boundary worsens one factor, move the boundary responsible for the current bottleneck; retaining that bottleneck cannot improve the objective as the other factor shrinks.

Pattern: Two pointers at opposite ends.

Simple idea: Width gets smaller after every move. Move the shorter wall because the shorter wall limits the current area. Moving the taller wall cannot improve that limit.

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

   while left < right:
      height = min(heights[left], heights[right])
      best = max(best, height * (right - left))
      if heights[left] < heights[right]:
         left += 1
      else:
         right -= 1

   return best

Cost: $O(n)$ time and $O(1)$ space.