Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Container With Most Water

Pick the two lines that hold the most water between them. Two pointers moving inwards from both ends solve it in O(n), with a proof of why it is safe.

mediumPattern: Two Pointers

Updated Short read: 5 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(1)
Two pointersO(n)O(1)

The problem

You are given an array of heights. Each one is a vertical line standing on a flat floor, one unit apart from its neighbours. Choose two lines so that, together with the floor, they form a container holding as much water as possible, and return that amount.

Water can only rise as high as the shorter of the two lines, so the amount held is:

area = (distance between the lines) × (height of the shorter line)
[1, 8, 6, 2, 5, 4, 8, 3, 7]   →  49    (lines at index 1 and 8: 7 wide × 7 high)
[1, 1]                        →  1
[4, 3, 2, 1, 4]               →  16    (the two outer lines: 4 wide × 4 high)

The lines in between do not matter. They are thin, so they take up no room in the container.

Approach 1: brute force

Work out the area for every pair of lines and keep the largest.

JavaScript

function maxAreaBruteForce(heights) {
  let best = 0;
  for (let left = 0; left < heights.length; left++) {
    for (let right = left + 1; right < heights.length; right++) {
      const width = right - left;
      const height = Math.min(heights[left], heights[right]);
      best = Math.max(best, width * height);
    }
  }
  return best;
}

Python

def max_area_brute_force(heights):
    best = 0
    for left in range(len(heights)):
        for right in range(left + 1, len(heights)):
            width = right - left
            height = min(heights[left], heights[right])
            best = max(best, width * height)
    return best

Time O(n²): there are about n²/2 pairs. Space O(1).

Approach 2: two pointers

Start with the widest container there is: one pointer on the first line and one on the last. Every other container is narrower, so the only way to beat this one is with a taller shorter side. That gives a simple rule: move the pointer that is on the shorter line, and keep track of the best area seen. This is the opposite-ends form of the two pointers pattern.

JavaScript

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

Python

def max_area(heights):
    left = 0
    right = len(heights) - 1
    best = 0
 
    while left < right:
        width = right - left
        height = min(heights[left], heights[right])
        best = max(best, width * height)
 
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

Walkthrough

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

left (height) right (height) Width Area best Move
0 (1) 8 (7) 8 8 8 left, it is shorter
1 (8) 8 (7) 7 49 49 right
1 (8) 7 (3) 6 18 49 right
1 (8) 6 (8) 5 40 49 right (a tie)
1 (8) 5 (4) 4 16 49 right
1 (8) 4 (5) 3 15 49 right
1 (8) 3 (2) 2 4 49 right
1 (8) 2 (6) 1 6 49 right; pointers meet

Eight areas were calculated instead of the 36 the brute force would need.

Time O(n): each step moves one pointer one place, and they meet after n - 1 steps. Space O(1).

Why moving the shorter line is safe

Moving a pointer throws away every container that uses the line it was on. The method is only correct if none of those could have been the answer.

Say the left line is the shorter one, with height h. Consider any container that still uses this left line but pairs it with some other line further in:

  • It is narrower than the current container, because the other line is closer.
  • Its water level is at most h, because the left line is one of its sides and water cannot rise above the shorter side.

Narrower and no taller means no bigger. The current container, which has already been measured, is the best one the left line will ever be part of. Dropping that line loses nothing.

Moving the taller line instead would be a mistake: the shorter line would still cap the height while the width shrank, so the area could only go down, and the containers skipped might include the answer.

When the two lines are the same height, either pointer can move. Any better container must use two lines both taller than these, so both will have to move eventually.

How this differs from Trapping Rain Water

The two problems look alike but ask different questions. Here you choose two lines and ignore everything between them. In Trapping Rain Water the bars are solid, and you add up the water sitting above every bar. Both are solved by two pointers that always advance the shorter side, for closely related reasons.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxArea([4, 3, 2, 1, 4])); // 16

Python

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
print(max_area([4, 3, 2, 1, 4]))  # 16

The comment after each line is the result you should see.

Common mistakes

  • Using the taller line for the height. Water spills over the shorter side, so the height is Math.min of the two.
  • Moving the taller pointer, or always moving both. Either can step past the best pair.
  • Measuring width as right - left + 1. The width is the gap between the lines, not the number of lines: lines at index 1 and 8 are 7 apart.
  • Trying to sort the array. The positions are part of the problem. Sorting destroys the widths.

Original problem: LeetCode 11: Container With Most Water