Skip to content
16-Week DSA Roadmap
LeetCode #11MediumProblem 3 of 8

Container With Most Water

Pick two walls that, together with the ground, hold the most water, without measuring every pair.

  • Converging two pointers
  • Greedy pointer move

Before this, know: Arrays and indexes, Min and max of two numbers

The problem in plain English

You get a list height. Each number is a vertical wall standing at that index (position). Pick two walls. Together with the ground they form a container. How much water can the best container hold?

The water in a container is a rectangle:

  • its width is the distance between the two walls: right − left;
  • its height is the shorter of the two walls. Any higher and the water spills over the short side.

So area = width × shorter wall. Here is height = [2, 6, 3, 5, 1]:

206132531410
Walls 1 and 3 are 3 − 1 = 2 apart, and the shorter of them is 5 tall, so they hold 2 × 5 = 10. That's the best possible here.

The rules that matter:

  • The walls in between don’t block anything. Only the two chosen walls count.
  • You can’t tilt the container. Water stops at the shorter wall.
  • There are at least 2 walls. Heights can be 0.

Before you code: think it through

Start with the widest container: the first and last walls. Width can only shrink from here, so the only way to do better is to find taller walls. Which wall should we give up?

Back to height = [2, 6, 3, 5, 1]. Walls 0 and 4 hold 4 × min(2, 1) = 4 × 1 = 4. Wall 4 (height 1) is the shorter one, so it goes (the reason comes in a moment), and right moves to wall 3. Here is the next container:

20613253146leftright
Walls 0 and 3: width 3, the left wall (2) is shorter, so the area is 3 × 2 = 6. Any other container that uses wall 0 is narrower, and its water still can't rise above 2.

Pause and think

In the picture, could pairing wall 0 (height 2) with wall 1 or wall 2 ever beat 6?

That’s the whole trick, and the reason we always move the shorter wall:

  • The shorter wall caps the water. Moving the taller wall makes the container narrower while the cap stays the same (or gets lower), so the area can only shrink. That move can never help.
  • Moving the shorter wall also makes it narrower, but the new wall might be taller and raise the water. It’s the only move that has a chance.

Approach 1: Brute force

Measure every pair of walls and keep the biggest area.

Brute force: measure every pair

height = [2, 6, 3, 5, 1]

height (each bar is a wall)
2061325314
variables
width
—
water level
—shorter wall
area
—
best
0
  • Wall i
  • Wall j
  • Best container

Try every pair of walls: wall i on the left, wall j somewhere to its right. Keep the biggest area.

Step 1 / 12

Which line is running?

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

Brute force

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 = (j - i) * Math.min(height[i], height[j]);      best = Math.max(best, area);    }  }  return best;}
def max_area(height):    best = 0    for i in range(len(height)):        for j in range(i + 1, len(height)):            area = (j - i) * min(height[i], height[j])            best = max(best, area)    return best

Why is it slow?

With 5 walls there are 4 + 3 + 2 + 1 = 10 pairs. LeetCode allows 100,000 walls: about 100,000 × 99,999 ÷ 2 ≈ 5 billion pairs. That’s O(n²) (“O of n squared”): double the walls, four times the work. Way too slow.

The pattern: greedy pointer move

The two pointers start at both ends and move toward each other, like in Valid Palindrome. The new idea is which pointer to move. A choice that grabs the best-looking option at each step is called greedy, and here we can prove the greedy choice is always safe.

Pattern

Greedy pointer move

Template

Use it when: two pointers start at both ends and, at each step, one side clearly limits the answer, so moving the other side can never help.

Signal words

  • “maximum area”
  • “two lines / walls”
  • “width × height”
  • “move the smaller side”
  • “maximize over pairs”

Approach 2: Move the shorter wall

  1. Put left on the first wall and right on the last wall. Set best = 0.
  2. Measure: area = (right − left) × min(height[left], height[right]). Update best.
  3. If the left wall is shorter, move left one step right. Otherwise move right one step left.
  4. Repeat while left is smaller than right. Return best.

The blue shading is the water for the current pair; the dashed green box is the best container so far. Faded walls have been ruled out for good. Watch how the pointer that moves is always on the shorter wall.

Two pointers: move the shorter wall

height = [2, 6, 3, 5, 1]

height (each bar is a wall)
2061325314leftright
variables
width
4
water level
—shorter wall
area
—
best
0
  • left wall
  • right wall
  • Ruled out
  • Best container

Start with the widest container possible: left on the first wall, right on the last wall. Width is as big as it will ever be.

Step 1 / 10

Which line is running?

function maxArea(height) {  let left = 0;Running now:   let right = height.length - 1;  let best = 0;  while (left < right) {    const width = right - left;    const area = width * Math.min(height[left], height[right]);    best = Math.max(best, area);    if (height[left] < height[right]) {      left++; // the left wall is the shorter one: move it    } else {      right--; // the right wall is shorter (or they tie): move it    }  }  return best;}

Try the equal walls example [4, 3, 2, 1, 4]: the very first container (width 4, height 4) is already the best, and the algorithm keeps it.

The code, line by line

Move the shorter wall

function maxArea(height) {  let left = 0;  let right = height.length - 1;  let best = 0;  while (left < right) {    const width = right - left;    const area = width * Math.min(height[left], height[right]);    best = Math.max(best, area);    if (height[left] < height[right]) {      left++; // the left wall is the shorter one: move it    } else {      right--; // the right wall is shorter (or they tie): move it    }  }  return best;}
def max_area(height):    left, right = 0, len(height) - 1    best = 0    while left < right:        width = right - left        area = width * min(height[left], height[right])        best = max(best, area)        if height[left] < height[right]:            left += 1  # the left wall is the shorter one: move it        else:            right -= 1  # the right wall is shorter (or they tie): move it    return best

On LeetCode it’s var maxArea = function(height) in JavaScript, and def maxArea(self, height) inside class Solution in Python.

  • Line 1: the function takes the list of wall heights.
  • Lines 2–4 (JS) / lines 2–3 (Python): pointers on the first and last walls, and best, the biggest area seen so far (0 to begin with).
  • Line 5 (JS) / line 4 (Python): loop while the two pointers are on different walls.
  • Line 6 (JS) / line 5 (Python): the width is the distance between the walls.
  • Line 7 (JS) / line 6 (Python): the water rises only to the shorter wall, so multiply the width by min(...), the smaller of the two heights.
  • Line 8 (JS) / line 7 (Python): keep the bigger of best and this area. Math.max / max returns the larger of two numbers.
  • Lines 9–10 (JS) / lines 8–9 (Python): if the left wall is shorter, it has done its best, so move left inward.
  • Lines 11–12 (JS) / lines 10–11 (Python): otherwise the right wall is shorter, or they’re equal, so move right inward. When they’re equal, moving either one is fine: both are capped at that height.
  • The last line: return the best area.

Dry run

height = [2, 6, 3, 5, 1]:

leftrightwidthmin heightareabestshorter wall → move
044min(2, 1) = 144right (1)
033min(2, 5) = 266left (2)
132min(6, 5) = 51010right (5)
121min(6, 3) = 3310right (3), pointers meet
height = [2, 6, 3, 5, 1]

The left = 1, right = 3 row is the answer: two tall walls fairly close together beat the very wide container in the first row (left = 0, right = 4), whose water was held down by the 1-high wall.

Complexity

Brute force

Time

O(n²)

Every pair of walls is measured: about n × n ÷ 2 pairs.

Space

O(1)

Just i, j and best.

Move the shorter wall

Time

O(n)

Each step moves one pointer one wall inward, so after n − 1 steps they meet. 100,000 walls ≈ 100,000 steps instead of 5 billion.

Space

O(1)

Only left, right and best, however many walls there are.

Common mistakes and edge cases

What to say out loud:

  1. “Area is width times the shorter wall.”
  2. “Brute force measures every pair: O(n²).”
  3. “Start widest. The shorter wall limits the water, and any narrower container with it can’t be bigger, so I can drop it and move that pointer.”
  4. “Each step drops one wall, so O(n) time and O(1) space.”

The interviewer will almost always ask why moving the shorter side is safe. Practise saying the proof in your own words: “the short wall has already met its widest partner, and closer partners can’t raise the water above it”.

Likely follow-up questions:

  • “What if both walls are equal?” Move either. Both are capped at that height, so neither can do better with a closer partner.
  • “How is this different from Trapping Rain Water?” There, every bar counts and water sits on top of each bar; here only the two chosen walls matter.

Related problems: