Container With Most Water

Difficulty: Medium

Problem

Imagine you have a row of vertical lines (walls) of different heights. You want to pick TWO lines that, together with the ground, form a container that can hold the most water.

The key insight: water can only rise as high as the SHORTER of the two walls you pick. So you need to balance between tall walls and wide containers!

Example

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: Pick lines at index 1 (height 8) and index 8 (height 7). The water can only rise to height 7 (the shorter wall). Width = 8 - 1 = 7 positions. Area = 7 × 7 = 49 square units.

Brute-force approach

Try every pair of lines and calculate the area between them.

Steps

  1. For each pair of lines (i, j)
  2. Calculate width = j - i
  3. Calculate height = min(height[i], height[j])
  4. Track maximum area

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Checking every pair is slow
  • Many pairs can't possibly be optimal
  • Width decreases as we go inward

Optimal approach

Key insight: Area is limited by shorter line. Moving shorter line inward might find taller one. Moving taller line can only make area smaller!

Start with widest container, move the shorter line inward to potentially find taller lines.

Steps

  1. Start with left=0, right=n-1
  2. Calculate area with current pointers
  3. Move the pointer at shorter line
  4. Track maximum area found

Time complexity: O(n) · Space complexity: O(1)