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
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]:
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.
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:
Pause and think
No. With wall 1: width 1, height min(2, 6) = 2, area 2. With wall 2: width 2,
height min(2, 3) = 2, area 4. Every other partner is closer (smaller width)
and the water is still capped at 2 by wall 0. So wall 0 has already given its
best. We can throw it away and move left.
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.
Measure every pair of walls and keep the biggest area.
Brute force: measure every pair
height = [2, 6, 3, 5, 1]
- 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.
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 bestWith 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 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
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”
- Put
lefton the first wall andrighton the last wall. Setbest = 0. - Measure:
area = (right − left) × min(height[left], height[right]). Updatebest. - If the left wall is shorter, move
leftone step right. Otherwise moverightone step left. - Repeat while
leftis smaller thanright. Returnbest.
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]
- 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.
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.
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 bestOn 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
bestand this area.Math.max/maxreturns 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
leftinward. - Lines 11–12 (JS) / lines 10–11 (Python): otherwise the right wall is
shorter, or they’re equal, so move
rightinward. When they’re equal, moving either one is fine: both are capped at that height. - The last line: return the best area.
height = [2, 6, 3, 5, 1]:
| left | right | width | min height | area | best | shorter wall → move |
|---|---|---|---|---|---|---|
| 0 | 4 | 4 | min(2, 1) = 1 | 4 | 4 | right (1) |
| 0 | 3 | 3 | min(2, 5) = 2 | 6 | 6 | left (2) |
| 1 | 3 | 2 | min(6, 5) = 5 | 10 | 10 | right (5) |
| 1 | 2 | 1 | min(6, 3) = 3 | 3 | 10 | right (3), pointers meet |
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.
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.
What to say out loud:
- “Area is width times the shorter wall.”
- “Brute force measures every pair: O(n²).”
- “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.”
- “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:
- Two Sum II: the same “rule out one end per step” idea, using a sum.
- Valid Palindrome: converging pointers without a choice of which to move.
- The greedy pointer move pattern in the week overview.