#21

Container With Most Water

medium

arraytwo-pointersgreedy

You are given an integer array height of length n. Each value height[i] is a vertical line drawn from (i, 0) to (i, height[i]).

Pick two of these lines so that, together with the x-axis, they form a container holding the most water. Return that maximum amount of water.

The container's area is min(height[i], height[j]) * (j - i) for the chosen pair i < j — the shorter line caps the water level, and the horizontal distance sets the width. The container cannot be tilted.

Example

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

Output: 49

Lines at index 1 (height 8) and index 8 (height 7) give min(8, 7) (8 - 1) = 7 7 = 49.

Constraints

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

Intuition

A first pass just measures every pair of lines as the container's two walls and keeps the largest. The water a pair holds is min(height[i], height[j]) × (j − i) — the shorter wall caps the level, the gap between them sets the width.

function maxArea(height) {
  let best = 0;
  // Try every pair of lines as the container's two walls.
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      // Water is capped by the shorter wall, spread over the width between them.
      const area = Math.min(height[i], height[j]) * (j - i);
      best = Math.max(best, area); // keep the largest seen
    }
  }
  return best;
}

Brute force — measure every pair of lines: O(n²).

This is O(n²) — far more work than necessary. Can we do better?

Start at the widest pair, one line at each end. Width is at its maximum here, so any inward move can only shrink it. Notice the area is capped by the shorter wall: moving the taller wall in keeps that same cap while losing width, so it can never improve. The only move that might help is advancing the shorter wall, hoping to trade a little width for a taller cap.

That converging-from-both-ends sweep is the Two pointers pattern: one O(n) pass that safely discards a wall at every step instead of re-measuring every pair.

Walking it through:

height = [1, 8, 6, 2, 5, 7] — converging two pointers

left↓

right↓

min(1,7)·5 = 5 → left shorter, left++

Widest pair: best = 5. The left wall (1) caps it, so move the shorter wall in.

left↓

right↓

min(8,7)·4 = 28 → right shorter, right--

best = 28. Now the right wall (7) is the shorter one.

left↓

right↓

min(8,5)·3 = 15 → right shorter, right--

A failing move: 15 < 28. Narrower and no taller — keep moving the shorter (right) wall.

left↓

right↓

min(8,2)·2 = 4 → right shorter, right--

Still short of 28; the right wall stays the binding constraint.

left↓

right↓

min(8,6)·1 = 6 → right--, pointers meet

Last pair before they cross. Nothing beat 28. Answer: 28.

Optimization

Two pointers

Start with the widest possible container — pointers at both ends. Its area is min(height[left], height[right]) * (right - left).

Any move inward shrinks the width, so it's only worth moving if the new line can be taller. The shorter of the two lines is the binding constraint, so advance whichever pointer is shorter (ties: either works) and recompute, tracking the maximum.

O(n) time, O(1) space.

function maxArea(height) {
  // Start with the widest possible container: one wall at each end.
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    // Water level is set by the shorter wall, spread over the gap between them.
    const area = Math.min(height[left], height[right]) * (right - left);
    if (area > best) best = area;
    // Moving the taller wall can't lift the cap, so always advance the shorter one,
    // hoping to trade a little width for a taller wall.
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

Complexity analysis

Time complexity: O(n). Here's why:

The two pointers start at opposite ends and only ever move toward each other.
Each step measures one pair in O(1) and then advances exactly one pointer.

The pointers together cover the array once before they meet, so the whole scan is O(n) — no sort, no nesting.

Space complexity: O(1). Here's why:

It keeps only the two pointers and a running best.
The input is read in place — nothing is copied or accumulated.

There is no auxiliary structure that grows with the input, so the extra space is constant — O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
height = [2,0]	0	Smallest input, zero-area: a flat end caps the shorter wall — min(2,0)·1.
height = [3,3,3]	6	All equal: width wins, so the outermost pair is best — min(3,3)·2.
height = [1,9,1]	2	A tall middle wall is wasted — the short ends cap the level — min(1,1)·2.
height = [4,1,4]	8	Duplicate end walls beat the deep valley between them — min(4,4)·2.
height = [6,0,6]	12	Tall ends over a flat middle — min(6,6)·2.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor