The problem
Each number is the height of a vertical line (a fence post) placed one unit apart. Pick two posts so that, with the ground, they hold the most water. Water level is limited by the shorter post; the amount is (shorter height) × (distance between them).
Input: [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (posts of height 8 and 7, 7 apart)
Picture it
Picture fence posts with a tarp stretched between two of them: water fills up to the top of the shorter post. Start with the widest pair (first and last). Moving the taller post inward can never help, since the water is still capped by the short one and the width shrinks. So we always move the shorter post inward, hoping to find a taller one.
How to recognise it
- You choose two positions and the score depends on the distance between them and the smaller of the two values.
- Starting with the pair farthest apart gives the widest container. Moving inwards always loses width, so you need a reason to believe you can gain height.
- That reason exists: the shorter side limits the water, so only replacing it could ever help.
- n is up to 10^5, so checking every pair is too slow.
Start with brute force
Try every pair of posts and keep the largest area.
def max_area_brute(h):
best = 0
for i in range(len(h)):
for j in range(i + 1, len(h)):
best = max(best, (j - i) * min(h[i], h[j]))
return best
There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). With n = 10^5 that is about 5 × 10^9 pairs, far too slow.
From brute force to the idea
- Start as wide as possible. Put
lon the first post andron the last. This is the widest container, so record its area. - Look at the shorter post. Say
h[l]is shorter. Any container using postlwith a partner closer thanris narrower, and its water level is still at mosth[l]. So none of them can beat the one you just measured. - Discard it. Every remaining pair with post
lis no better than one you have seen, so movelright. Ifh[r]is the shorter one, moverleft by the same argument. - Ties are safe either way. When both posts are equal, the code moves
r. Any better container would need both of its posts taller than this height, so neither of these two posts can be part of it. - Repeat until they meet. Each step drops one post for good, and the best pair is never dropped before it is measured.
This is the key idea: always move the shorter post inwards, because it cannot do better with a narrower partner.
The key idea
Area = min(h[l], h[r]) × (r − l). Always move the shorter side inward; you never skip a better pair. O(n).
Python solution
def max_area(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, (r - l) * min(h[l], h[r]))
if h[l] < h[r]:
l += 1
else:
r -= 1
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every pair is measured | O(1): two indices and the best |
| Two pointers (shown code) | O(n): one pointer moves inwards on each step, at most n − 1 steps | O(1): two indices and the best |
Edge cases
- Two posts (
[1, 1]): returns 1, the only container. - All the same height (
[4, 4, 4, 4]): returns 12, the two end posts, measured on the first step. - Zero heights (
[0, 0]): returns 0; a post of height 0 holds nothing. - Fewer than two posts:
[5]and[]return 0. LeetCode guarantees at least two. - Best pair is not at the ends (
[1, 8, 6, 2, 5, 4, 8, 3, 7]): returns 49, from the 8 at position 1 and the 7 at position 8. The short end post 1 is dropped first.
Common mistakes
- Moving the taller post. The water is still capped by the short post, and the width shrinks, so the code misses better pairs: on the example above it returns 8 instead of 49.
- Using
max(h[l], h[r])for the water level. The water spills over the shorter post. - Moving both pointers at once on a tie, then worrying it is wrong. It is safe, by the same argument, but it is not needed.
- Confusing this with Trapping Rain Water, which adds up water over every position instead of picking one pair.
Suppose each post takes up one unit of width, so the water between posts i and j is min(h[i], h[j]) × (j − i − 1). Find the largest amount. For the example [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 42. Does the same idea still work? Describe your approach, then write it if you like.
Compare with our answer
Yes. The argument never used the exact width, only that moving inwards makes it smaller. With j − i − 1 that is still true, so the shorter post is still useless with any narrower partner and can be dropped.
def max_area_thick(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, (r - l - 1) * min(h[l], h[r]))
if h[l] < h[r]:
l += 1
else:
r -= 1
return best
Neighbouring posts now hold 0. Time O(n), space O(1).
A strong answer mentions: re-checking the discard argument rather than assuming it, that width still shrinks as the pointers move inwards, and that neighbours now give 0.
1. People stand in a line, and the score of choosing two of them is (shorter height) × (number of positions between them). Which approach finds the best score fastest?
It is the same score shape: width shrinks as you move in, and the shorter value caps the height, so the shorter end can be discarded. The stack belongs to "next taller" problems, and sorting would take O(n log n) at best.
2. Why can the shown code discard the shorter post without checking it against the posts in between?
Every container it could still form is narrower than the one just measured, and its water level cannot rise above its own height. The middle posts may be taller, but that does not help a container limited by the short post.
3. A learner changes the test to if h[l] > h[r]: l += 1, so the taller post moves. What does it return for [1, 8, 6, 2, 5, 4, 8, 3, 7]?
The 1 at the left end is never the taller post, so l never moves while r walks left. Every container uses the post of height 1, and the widest has area 8 × 1 = 8. The right answer is 49.
Score 60% or more and the lesson is marked complete.