Repository navigation
043 — Container With Most Water
LeetCode 11 · Medium. Given n non-negative integers height, where height[i] is the height of a vertical line at position i, find two lines that, together with the x-axis, form a container holding the most water. Return the maximum amount of water it can store.
Picture a row of fence posts of different heights planted along a line, and you're stretching a tarp between any two of them to catch rainwater. No matter how tall one post is, the tarp can only rise as high as the shorter of the two posts you pick — the extra height on the taller one is wasted, water just spills over the short side. That's the whole game: given two posts, the water they hold is min(shorter height) × (distance between them).
Now suppose you start with the two outermost posts and want to know whether some other pair might hold more. There's really only one lever worth pulling: move the pointer standing on the shorter post inward. Moving the taller post's pointer inward can only shrink the width while the height ceiling stays capped by that same short post (or something even shorter) — a guaranteed loss, never a gain. Moving the shorter post's pointer inward at least has a chance at a taller ceiling, even though it costs you some width. So you always move the pointer standing at the bottleneck.
"Container" / "maximum area between two lines" / "two lines, maximize the space between them" is a direct verbal cue for two pointers converging from both ends of the array. Whenever an answer is shaped like min(a, b) × distance, the shorter of a/b is the bottleneck — and moving the pointer sitting on that bottleneck is the only move that can possibly improve the answer, which is exactly what licenses the inward-converging sweep instead of checking every pair.
Check every pair of lines and compute the area each pair would enclose.
func maxAreaBruteForce(_ height: [Int]) -> Int {
var best = 0
for i in 0..<height.count {
for j in (i + 1)..<height.count {
let width = j - i
let area = min(height[i], height[j]) * width
best = max(best, area)
}
}
return best
}Big-O: O(n²) time — every pair of lines is checked. O(1) extra space.
Start pointers at the two outermost lines. At each step, record the area, then advance whichever pointer stands on the shorter line — that's the only move that can ever raise the ceiling.
func maxArea(_ height: [Int]) -> Int {
var left = 0
var right = height.count - 1
var best = 0
while left < right {
let width = right - left
let shorterWall = min(height[left], height[right])
best = max(best, shorterWall * width)
if height[left] < height[right] {
left += 1 // the left wall is the bottleneck — only moving it can raise the ceiling
} else {
right -= 1 // the right wall is the bottleneck (or they're tied) — move it instead
}
}
return best
}Big-O: O(n) time — the pointers together take at most n steps to meet. O(1) extra space.
The brute force checks every pair because, without more information, it has no way to know a given pair is safe to skip. But the formula min(height[l], height[r]) × (r - l) has a hidden monotonic property: whichever wall is shorter is the only thing capping the area, so any pair formed by moving the taller wall's pointer inward is provably no better than the pair you're already standing on (the width shrinks, and the height ceiling can't improve — it's still bounded by the same short wall, or an even shorter one). That guarantee lets you discard an entire sweep of candidate pairs with a single comparison, collapsing the O(n²) all-pairs check into a single O(n) inward walk.
- Two Pointers — the converging-inward-pointers pattern this problem is a canonical worked example of.
-
Arrays & Strings — the
heightarray being scanned. - Greedy — "always move the pointer that can't possibly help you keep it in place" is a greedy exchange argument: swapping the taller wall for a shorter candidate is never worse than the alternative.
Container With Most Water is two fence posts holding up a tarp — the shorter post is always the ceiling, so it's always the one worth moving.
Using the formula area = min(height[l], height[r]) × (r - l), prove to yourself why moving the pointer on the taller wall inward can never produce a better answer than the pair you're currently standing on. Then construct a small 4-element height example where moving the shorter wall's pointer sometimes helps and sometimes doesn't — but never hurts your best-seen answer so far.