Container With Most Water

MediumTwo PointersArrayTwo PointersGreedy

Problem

You are given an array where each value is the height of a vertical line at that index. Pick any two lines so that, with the x-axis, they form a container; the water it holds is bounded by the shorter line, over the distance between them. Find the pair that holds the most water.

Example. For [1, 8, 6, 2, 5, 4, 8, 3, 7], the best pair is the lines at index 1 (height 8) and index 8 (height 7): width 7 times the shorter height 7 gives an area of 49.

Key idea

Testing every pair of lines costs O(n²). A two-pointer approach starting at the outer edges does much better, since at every step it rules out a whole set of possibilities in one move. Place a pointer at each end and compute the current area, limited by the shorter line. Moving the taller line's pointer inward only shrinks the width while the height stays capped by the same shorter line, so the area cannot improve. Moving the shorter line's pointer inward also shrinks the width, but it has a chance of finding a taller line and a better bound. So the only move worth making is advancing the pointer at the shorter side, discarding it as a candidate since nothing paired with it going forward could beat what has already been checked.

Solution

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let best = 0;

  while (left < right) {
    const width = right - left;
    const boundedHeight = Math.min(height[left], height[right]);
    best = Math.max(best, width * boundedHeight);

    // always advance the shorter side; moving the taller one cannot improve the area
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return best;
}

Complexity

  • Time: O(n). The pointers move toward each other and the array is scanned once.
  • Space: O(1). Only two indices and a running maximum are tracked.

Watch out for

  • Always move the pointer at the shorter line; moving the taller one is a common mistake that can skip the true answer.
  • Recompute the area before moving a pointer, using the heights at the current positions.
  • When the two heights are equal, either pointer can move; both are safe.

Pattern

This is a greedy two-pointer elimination pattern: at each step, one candidate is proven unable to lead to a better answer, so it is safely discarded. The same reasoning underlies Trapping Rain Water and other problems that bound an area or volume by two boundary values.

Related questions