Container With Most Water

Difficulty: Medium

You're given the heights of a row of vertical lines, evenly spaced one unit apart. Pick any two of these lines — together with the ground between them — to form a container. The container's walls are as tall as the shorter of your two chosen lines (water would spill over the shorter side), and its width is the distance between them.

Find the two lines that create the container able to hold the most water, and return that amount.

Examples

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

Picking the lines of height 8 (index 1) and height 7 (index 8) gives a width of 7 and a wall height of min(8, 7) = 7, for an area of 49 — the best possible.

Input: height = [1, 1]
Output: 1

There's only one pair to choose, giving min(1, 1) * 1 = 1.

Input: height = [4, 3, 2, 1, 4]
Output: 16

The two outer lines, both height 4, give min(4, 4) * 4 = 16.

Constraints

2 <= height.length <= 10^5
0 <= height[i] <= 10^4

Approach

The direct approach checks every possible pair of lines and keeps track of the best area — correct, but it repeats a lot of comparisons.

A faster approach uses two pointers starting at the two ends of the list, which gives the widest possible container to start. At each step, compute the area, then move whichever pointer is on the shorter line inward. Moving the taller line can never produce a better result: the width only shrinks, and the shorter line still limits the height either way. Moving the shorter line is the only move that has any chance of finding a taller wall and a bigger area, so this pass through the list once is enough.

Solutions

Brute Force — Check Every Pair

Compute the area for every possible pair of lines, and keep track of the largest one seen.

function maxArea(height) {
  let best = 0;
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const area = Math.min(height[i], height[j]) * (j - i);
      best = Math.max(best, area);
    }
  }
  return best;
}

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

Optimal — Two Pointers

Start with one pointer at each end, the widest container possible. At each step, record the area, then move whichever pointer sits on the shorter line inward — that's the only move that could possibly improve things.

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

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

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return best;
}

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