LeetCode 11 · Two Pointers

Container With Most Water, explained with a picture

Two fence posts holding water.

MediumTwo Pointers
▶ Watch it step by step

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

  1. Start as wide as possible. Put l on the first post and r on the last. This is the widest container, so record its area.
  2. Look at the shorter post. Say h[l] is shorter. Any container using post l with a partner closer than r is narrower, and its water level is still at most h[l]. So none of them can beat the one you just measured.
  3. Discard it. Every remaining pair with post l is no better than one you have seen, so move l right. If h[r] is the shorter one, move r left by the same argument.
  4. 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.
  5. 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 best

In 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

ApproachTimeSpace
Brute forceO(n²): every pair is measuredO(1): two indices and the best
Two pointers (shown code)O(n): one pointer moves inwards on each step, at most n − 1 stepsO(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.
Your turn: thick posts

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.

Check what stuck

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?

2. Why can the shown code discard the shorter post without checking it against the posts in between?

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]?

Score 60% or more and the lesson is marked complete.