05. Container With Most Water

Difficulty:MediumPattern:Two Pointers ShrinkingTime:O(n)Space:O(1)

Given an integer array height of length $n$, find two lines that together with the x-axis form a container that holds the most water.

How It Works & Algorithmic Design

Solves using Two Pointers Shrinking Boundary:

Pointers: Position left = 0 and right = height.length - 1.
Area Calculation: width = right - left. Area = Math.min(height[left], height[right]) * width.
Max Update: maxWater = Math.max(maxWater, area).
Pointer Movement Strategy: To potentially find a taller boundary that compensates for reduced width, move the pointer that points to the shorter height (if (height[left] < height[right]) left++ else right--).

Why This Approach Works Best

Evaluating all pairs of lines takes $O(n^2)$ time. Moving the shorter pointer guarantees that higher potential areas are checked while eliminating inferior choices in $O(n)$ time and $O(1)$ space.

Example Walkthrough

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Heights of vertical lines.

Optimal Pair: Index 1 (height 8) and Index 8 (height 7)

Width = 8 - 1 = 7. Area = min(8, 7) * 7 = 49.

Output: 49

Maximum area of water contained.

Answer: Container with most water using two pointers

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let maxWater = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    maxWater = Math.max(maxWater, h * w);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return maxWater;
}

💡 Calculate area and always move the pointer pointing to the shorter vertical line.

Key Takeaways

Always move the pointer corresponding to the shorter boundary line.
Width continuously decreases, so height must increase to improve area.
Runs in linear $O(n)$ time and $O(1)$ space.