Container With Most Water: The Greedy Two Pointers Proof That Makes O(n) Obvious
Solve Container With Most Water with greedy two pointers: why moving the shorter wall is always safe, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Container With Most Water looks like a geometry puzzle, but it's really a lesson in proving that you're allowed to skip work. There are n(n−1)/2 possible pairs of walls, and the optimal solution examines at most n−1 of them — one per loop iteration — while guaranteeing the answer is still exact.
That guarantee comes from a greedy argument so clean that interviewers use this problem specifically to see whether you can articulate it: moving the taller wall can never help, so always move the shorter one. Explain why that's true — not just recite it — and you've unlocked a whole family of two-pointer problems.
The problem
You're given an array height where height[i] is the height of a vertical line at position i. Pick two lines; together with the x-axis they form a container. Return the maximum amount of water any container can hold. Water level is capped by the shorter of the two walls, and you can't tilt the container.
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49 // walls at indices 1 and 8: min(8, 7) * (8 - 1) = 7 * 7 = 49The area formula does all the conceptual work in this problem:
area = min(height[i], height[j]) * (j - i)Two forces pull against each other: width (distance between the walls) and height (capped by the shorter wall). Every strategy for this problem is really a strategy for trading one against the other.
The brute force baseline
Check every pair, keep the best:
var maxArea = function(arr) {
let maxWater = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
const area = Math.min(arr[i], arr[j]) * (j - i);
maxWater = Math.max(maxWater, area);
}
}
return maxWater;
};This is O(n²) — roughly 5 billion pair checks for a 10⁵-element array, which times out on LeetCode. And unlike Two Sum, there's no hash map rescue: we're maximizing a function of two interacting properties, not looking up a fixed complement. The exit isn't a better data structure — it's a proof that most pairs can't possibly win.
The key insight: the shorter wall is exhausted
Start with both pointers at the extremes — the widest possible container. From here, every move shrinks the width by 1, so a move is only worth making if it might raise the height cap. That framing decides everything.
Say the left wall is shorter (arr[i] < arr[j]). Consider every other container that keeps this left wall and pairs it with something further in:
- Its width is strictly smaller — the walls are closer together.
- Its height cap is still at most
arr[i]— the min can never exceed the shorter wall, no matter how tall the new partner is.
Smaller width, same-or-lower cap: every remaining pair involving the shorter wall is guaranteed to lose to the container we just measured. So discard that wall forever — one pointer move eliminates all of its unexplored pairings at once. Moving the taller wall would be the opposite mistake: width shrinks while the shorter wall still caps the height, so the area can only get worse.
That's the greedy two pointers pattern: measure the current candidate, then prove one whole side of the search space can never contain the answer. Each of the n−1 moves safely throws away a batch of pairs, which is how O(n²) candidates collapse into an O(n) scan.
The optimal solution
This is exactly the algorithm the interactive visualizer steps through, line by line:
var maxArea = function(arr) {
let i = 0;
let j = arr.length - 1;
let maxWater = 0;
while (i < j) {
const area = Math.min(arr[i], arr[j]) * (j - i);
maxWater = Math.max(maxWater, area);
if (arr[i] > arr[j]) {
--j;
} else {
++i;
}
}
return maxWater;
};Three details worth internalizing:
- Measure before moving. Every iteration records the current container first, so the best pair is never skipped — it gets measured the moment both its walls are under the pointers.
- The comparison decides which wall is "used up".
arr[i] > arr[j]means the right wall is the limiter, so--j. Otherwise the left wall limits (or ties), so++i. - Ties go left, and that's fine. When
arr[i] === arr[j], both walls cap the height, so no wider container through either wall can beat the current one. Moving either pointer is safe; this implementation movesi.
Walkthrough: arr = [6, 2, 5, 4, 8, 1]
| Step | i | j | min height | width | area | maxWater | Move |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 5 | min(6, 1) = 1 | 5 | 5 | 5 | 6 > 1 → --j |
| 2 | 0 | 4 | min(6, 8) = 6 | 4 | 24 | 24 | 6 ≤ 8 → ++i |
| 3 | 1 | 4 | min(2, 8) = 2 | 3 | 6 | 24 | 2 ≤ 8 → ++i |
| 4 | 2 | 4 | min(5, 8) = 5 | 2 | 10 | 24 | 5 ≤ 8 → ++i |
| 5 | 3 | 4 | min(4, 8) = 4 | 1 | 4 | 24 | pointers meet → return 24 |
Step 1 shows the elimination in action: the right wall of height 1 caps its widest possible container at area 5, so one --j discards all four of its remaining pairings. Step 2 finds the answer — walls 6 and 8, area 24 — and steps 3–5 confirm nothing narrower beats it. Five measurements instead of fifteen pairs, and the answer is still exact.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | measures all n(n−1)/2 pairs |
| Greedy two pointers | O(n) | O(1) | each iteration retires one wall permanently; n−1 moves total |
The two-pointer version is optimal in both dimensions: every element must be looked at at least once (any unseen wall could be a record-breaker), so O(n) time is a floor, and two indices plus a running max is all the state it ever holds.
Common mistakes
- Moving the taller pointer. The most common bug, usually from intuition like "the tall wall is valuable, keep looking near it." Backwards — the tall wall isn't the constraint. Moving it shrinks width while the shorter wall still caps the height, so you can only do worse. Move the wall that's limiting you.
- Using
Math.maxfor the height. Water spills over the shorter wall. The cap isMath.min(arr[i], arr[j]); using the max silently inflates every area. - Computing width as
j - i + 1. The walls stand at positionsiandj; the water spans the gap between them, which isj - i. The+1off-by-one overstates every container by one column. - Stopping early when the area drops. Area is not monotonic as the pointers close in — in the walkthrough it goes 5 → 24 → 6 → 10 → 4. A dip proves nothing; run until
imeetsj. - Confusing it with Trapping Rain Water. That problem sums water trapped above every bar between many walls; this one picks exactly two walls and ignores everything in between. Same two-pointer skeleton, completely different accounting.
Where this pattern shows up next
The move that matters here — walking two pointers toward each other and proving each step discards only hopeless candidates — anchors a whole track of problems:
- Two Sum — the hash-map ancestor: same "kill the inner loop" goal, achieved with memory instead of a greedy proof.
- Two Sum II - Input Array Is Sorted — converging pointers again, but driven by sorted order instead of a min-height cap.
- Is Subsequence — two pointers moving in the same direction, matching greedily instead of shrinking a window.
- Find the Index of the First Occurrence in a String — pointer alignment across two sequences, the scanning cousin of this family.
Reading the proof is one thing; watching it fire is another. Step through it interactively and you'll see the water level, both pointers, and the discarded walls update on every line of the code above.
FAQ
Why do you always move the shorter pointer in Container With Most Water?
Because the shorter wall has no future. The area formula is min(height) × width, and the pointers start at maximum width — so every subsequent pairing of the shorter wall has strictly less width and a height cap that still can't exceed that wall. The container you just measured was the best one that wall could ever produce, which makes discarding it safe. Moving the taller wall instead shrinks width without lifting the cap, so it can never increase the area.
What is the time complexity of Container With Most Water?
The greedy two-pointer solution runs in O(n) time and O(1) space: each iteration moves exactly one pointer inward, so after at most n−1 iterations the pointers meet, and the algorithm keeps only two indices and a running maximum. The brute-force pair check is O(n²) time, which times out on large LeetCode inputs.
What happens when both walls have the same height?
Either move is correct. When height[i] equals height[j], both walls cap the container, so any wider pair through either wall is already beaten by the one just measured — meaning both walls are simultaneously "exhausted." The standard implementation folds ties into the else branch and moves the left pointer, which costs nothing beyond one extra iteration.
How is Container With Most Water different from Trapping Rain Water?
Container With Most Water chooses exactly two walls and computes one rectangle of water between them — bars in the middle are ignored, and the answer is a single max. Trapping Rain Water sums the water sitting on top of every bar, where each column's water depends on the tallest walls to its left and right. They share the two-pointer technique but answer different questions, and pattern-matching one onto the other is a classic interview trap.
Can the two-pointer solution miss the optimal pair?
No. A pointer only moves when its wall has been proven unable to participate in any better container, so the optimal pair always remains between the pointers until the iteration that measures it. Every discarded pair loses to a container already recorded, which is why the greedy shortcut returns the exact maximum, not an approximation.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.