Container With Most Water

Difficulty: Medium

Problem

Picture a row of vertical walls with varying heights standing on flat ground. Choose two of them so that the space between them can hold as much water as possible.

Water can only fill up to the height of the LOWER of the two walls, so you must trade off tall walls against a wide gap!

Example

Input: height = [3, 9, 2, 7, 4, 8, 1, 6]
Output: 36
Explanation: Use the walls at index 1 (height 9) and index 7 (height 6). The water level is capped by the lower wall, 6, and the gap is 7 - 1 = 6 wide, so the area is 6 × 6 = 36.

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)

Pseudocode

function maxArea(height):
    left = 0
    right = length(height) - 1
    best = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, h * width)

        if height[left] < height[right]:
            left = left + 1
        else:
            right = right - 1

    return best

Hints

  • Area = min(height[left], height[right]) * (right - left)
  • Start with the widest container (left=0, right=n-1)
  • Move the pointer at the shorter wall to potentially increase min-height
  • Track the maximum area seen so far

Complexity questions

Time to check all pairs of lines?

O(n²). Checking all n(n-1)/2 pairs = O(n²)

Time with two pointer approach?

O(n). Pointers meet in the middle after n steps total = O(n)

Space for both approaches?

O(1). Only a few variables (pointers, max) = O(1)

Why move the shorter line, not the taller?

Shorter line limits the height, moving taller only reduces width. The water level is always limited by the shorter line. If we move the taller line inward, we lose width but can't gain height - so we'd only make things worse!

Check your understanding of Container With Most Water

How is the container area calculated?

min(height[left], height[right]) × (right - left). Water level is limited by the SHORTER wall. Area = shorter height × width between the walls.

Given [1,8,6,2,5,4,8,3,7], which two lines give max area?

Lines at index 1 and 8. Index 1 (height 8) and index 8 (height 7): Area = min(8,7) × 7 = 49.

Why might a container with shorter walls hold MORE water?

If the shorter walls are farther apart, the extra width can compensate. Area = height × width. Sometimes walls that are far apart (large width) can hold more water than tall walls that are close together.

Related problems

Keep practising