DSAMotivator

Container With Most Water

MediumĀ·šŸ‘‰ Two PointersĀ·Open on LeetCode ā†—

Each array entry is the height of a vertical line on a flat surface. Pick two lines so that the water held between them is as large as possible, and return that volume.

height = [3, 9, 4, 2, 7, 8, 5]step 1/14
lā†“
rā†“
3
9
4
2
7
8
5
0
1
2
3
4
5
6

Start as wide as the array allows. From here width only shrinks, so any better container has to be taller.

1def max_area(height):
2    l, r = 0, len(height) - 1
3    best = 0
4    while l < r:
5        best = max(best, min(height[l], height[r]) * (r - l))
6        if height[l] < height[r]:
7            l += 1
8        else:
9            r -= 1
10    return best
Read the 14 steps as text
  1. 1Start as wide as the array allows. From here width only shrinks, so any better container has to be taller.
  2. 2min(3, 5) Ɨ 6 = 18. That's a new best.
  3. 3Left line 3 is shorter, so it caps every container it's in. Discard it.
  4. 4min(9, 5) Ɨ 5 = 25. That's a new best.
  5. 5Right line 5 is the shorter one (or tied), so nothing better remains for it. Discard it.
  6. 6min(9, 8) Ɨ 4 = 32. That's a new best.
  7. 7Right line 8 is the shorter one (or tied), so nothing better remains for it. Discard it.
  8. 8min(9, 7) Ɨ 3 = 21. Best stays 32.
  9. 9Right line 7 is the shorter one (or tied), so nothing better remains for it. Discard it.
  10. 10min(9, 2) Ɨ 2 = 4. Best stays 32.
  11. 11Right line 2 is the shorter one (or tied), so nothing better remains for it. Discard it.
  12. 12min(9, 4) Ɨ 1 = 4. Best stays 32.
  13. 13Right line 4 is the shorter one (or tied), so nothing better remains for it. Discard it.
  14. 14Pointers have met. The largest container holds 32.

Start with the obvious solution

Try every pair of lines, compute the water each pair holds, and keep the largest.

O(nĀ²) time, O(1) space

Why that isn't enough: It's correct but it never uses the one fact that makes the problem tractable: moving the taller wall inward can never help. Without that observation there is nothing to prune, so every pair has to be tested.

The idea

The area between two lines is min(left height, right height) Ɨ the distance between them. Two things fight each other: moving the lines apart adds width, but the shorter of the two caps the height.

Start as wide as possible ā€” first line and last line. Width will only ever shrink from here, so every future container has to win on height instead.

Now the key observation, and it is the whole problem: the shorter line is the binding constraint. Whatever you pair it with, the height can never exceed it, and the width can only get smaller. So the shorter line's best possible container is the one you're looking at right now. It can be discarded permanently.

That's why one pass works. Each step throws away a line and, with it, every pair that line was part of ā€” n steps eliminate all O(nĀ²) pairs.

The approach

  1. 1Put one pointer at each end and track the best area seen.
  2. 2Measure the current container: min of the two heights, times the gap between the indices.
  3. 3Move the pointer at the shorter line inward. Never the taller one ā€” moving the taller one keeps the same cap and loses width, so it can't improve anything.
  4. 4Stop when the pointers meet.

Complexity

Time
O(n)
Space
O(1)

Each pointer only ever moves toward the other, so together they take at most n steps.

Code

def max_area(height):
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        best = max(best, min(height[l], height[r]) * (r - l))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

What goes wrong

  • ā€¢Moving the taller line, or moving both. Both are strictly worse: the height is still capped by the shorter line and you've thrown away width for nothing.
  • ā€¢Thinking the tallest pair of lines wins. Two tall lines standing next to each other can easily lose to a short pair standing far apart ā€” the width matters just as much.
  • ā€¢Treating this like Trapping Rain Water. Same shape of input, completely different question: here the lines between the two you pick are irrelevant, there they're the entire answer.