Container With Most Water

Try It Yourself

Use the editor below to measure containers formed by two lines. The current area depends on the distance between the pointers and the shorter of their two heights.

Submit your implementation when it passes the examples. Decide which pointer can move without discarding a possible improvement.

Container With Most Water

mediumTwo Pointers · Greedy30 minLC 11

Problem

Each value in heights represents a vertical line at that index. Choose two lines that hold the greatest amount of water.

Return the maximum area. The area is the shorter height multiplied by the distance between the lines.

Example 1:

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

Output: 49

Example 2:

Input: heights = [1, 1]

Output: 1

Constraints

2 ≤ heights.length ≤ 100,000
0 ≤ heights[i] ≤ 10,000

0 attempts

Solution

Start with the widest possible container. Record its area, then move the pointer at the shorter line because keeping that shorter height cannot improve the area after the width shrinks.

Repeat until the pointers meet, preserving the greatest area seen.

function maxArea(heights) {
  let left = 0;
  let right = heights.length - 1;
  let maximum = 0;

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

    if (heights[left] <= heights[right]) left++;
    else right--;
  }

  return maximum;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	The two pointers move inward across the array once.
Auxiliary space	`O(1)`	The algorithm stores only pointer positions and the best area.