Container With Most Water

One comparison retires a whole wall

Here is a row of vertical lines, one per index: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Pick two of them. Together with the floor they make a container, and the water inside rises until it spills over the shorter line. The water it holds is

area = min(height[i], height[j]) × (j − i)

Find the pair that holds the most.

The obvious plan measures every pair. Nine lines give 36 pairs, which is nothing. LeetCode allows 100,000 lines, which gives n(n−1)/2 = 4,999,950,000 pairs. The brute force below measured about 13 million pairs per second in CPython on a fast laptop, so one input would take about six and a half minutes. No judge waits that long.

The two-pointer solution in this lesson measures 99,999 pairs for the same input, and it finished in about 10 milliseconds. It rests on one observation:

Start with the widest pair. Its shorter wall has just met its best possible partner, because every other partner is closer and the water can never rise above that wall. So one measurement retires that wall for good.

Each measurement retires one wall, and after n − 1 of them nothing is left to check. Most of this lesson is about why that is safe, because the proof is what lets you reuse the idea and spot when it breaks.

This lesson builds on Two Pointer Techniques, where converging pointers solve Two Sum II on sorted input, and on Foundation: Arrays & Strings: best here is a running summary (Move 1), and left and right start at opposite ends like the reversal pointers of Move 4. Two things are new. The input is not sorted, and the choice of which pointer to move comes from comparing the two heights, not from comparing a sum with a target. Why that choice is safe is the interesting question.

Read the contract

This is LeetCode 11: Container With Most Water. You get height, a list of n integers. Line i runs from (i, 0) up to (i, height[i]). Return the largest amount of water two lines can hold with the x-axis. The container may not be slanted. The limits are 2 ≤ n ≤ 10⁵ and 0 ≤ height[i] ≤ 10⁴.

Four details decide what you compute:

• Return a number. The judge wants the area, not the two indices.
• Only the two chosen lines matter. The lines between them have no thickness. They neither block the water nor take up room.
• Width is the distance, j − i. It counts the gaps between the lines, not the lines. Lines 3 and 5 are 2 apart.
• n ≥ 2, but heights can be 0. There is always at least one pair, and the answer can be 0.

Here is the best container for the example, lines 1 and 8. The # columns are its walls, the | lines are ignored, and ~ is water:

8     #                   |
7     #~~~~~~~~~~~~~~~~~~~|~~~~~~~#
6     #~~~|~~~~~~~~~~~~~~~|~~~~~~~#
5     #~~~|~~~~~~~|~~~~~~~|~~~~~~~#
4     #~~~|~~~~~~~|~~~|~~~|~~~~~~~#
3     #~~~|~~~~~~~|~~~|~~~|~~~|~~~#
2     #~~~|~~~|~~~|~~~|~~~|~~~|~~~#
1 |   #~~~|~~~|~~~|~~~|~~~|~~~|~~~#
  0   1   2   3   4   5   6   7   8   <- index

The water is 7 gaps wide and 7 levels deep, so the area is 49. Line 1 is 8 tall, but the water stops at 7, where line 8 ends.

Predict first: the two tallest lines are the 8s at indices 1 and 6. Is that pair the answer?

Every pair, honestly

Smell: you are maximizing a score over all pairs i < j, and one factor of that score (here, the width) only shrinks as a pair moves inward.

Write the slow version first. It is short, obviously correct, and it becomes the reference you test the fast version against.

def max_area_brute(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, min(height[i], height[j]) * (j - i))
    return best

print(max_area_brute([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49

It measures n(n−1)/2 pairs: O(n²) time and O(1) extra space. At 13 million pairs per second, the 4,999,950,000 pairs for n = 100,000 take about 385 seconds.

Where the time goes

Picture every pair as one cell of a triangle, the pair table. Row i holds the pairs whose left wall is i, and column j holds the pairs whose right wall is j. Here it is for a smaller input, with each cell holding that pair's area:

height = [1, 5, 7, 2, 6, 3]
              j=1  j=2  j=3  j=4  j=5
              (5)  (7)  (2)  (6)  (3)
i=0 (1)         1    2    3    4    5
i=1 (5)              5    4   15   12
i=2 (7)                   2   12    9
i=3 (2)                        2    4
i=4 (6)                             3

Look at row 0. Wall 0 is 1 tall, so every pair in that row holds at most 1 × width, and the widest cell, 5, has to be the best one in the row. The brute force still computes all five cells.

That observation is the whole speedup. If one measurement can tell you the best cell of an entire row, you can skip the rest of that row. The next section finds such a measurement at every step, not just for the shortest wall.

The shorter wall is finished

Predict first: start with the widest pair of the LeetCode example, (0, 8). The heights are 1 and 7, so the area is 8. Without measuring anything else, which of the two walls can you rule out of every future container, and why? What about the other wall?

That is the whole rule: measure the current pair, then retire the shorter wall by moving its pointer inward.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        best = max(best, area)
        if height[left] < height[right]:
            left += 1      # the left wall is shorter: it has met its best partner
        else:
            right -= 1     # the right wall is shorter, or they tie
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 49

Here is every iteration on the example, printed by running the code:

After step 8, left == right == 1 and the loop stops. Three things to notice:

• The answer appears at step 2, but the code cannot know that nothing better is coming. It keeps retiring walls until none are left.
• Step 3 is worse than step 2 (18 after 49). Retiring the shorter wall does not promise a better next pair. It promises that the pairs you skip are no better than one you already measured.
• Wall 1 never retires. It is 8 tall, the maximum, so it is never the strictly shorter side. At the step-4 tie (8 and 8), this code moves right.

Cost. Every iteration moves exactly one pointer by one step, so the gap right − left starts at n − 1, drops by 1 each time, and stops at 0. The loop runs exactly n − 1 times, whatever the heights: O(n) time. The pointers meet wherever the rule takes them, not necessarily in the middle (here, at index 1). Extra space is O(1): three integers and a temporary.

Your turn: trace max_area([2, 3, 4, 5, 18, 17, 6]). List the pairs it measures, give the result, and say whether it ever measures the two tallest walls, 18 and 17.

Why it never misses the answer

"Move the shorter one" sounds like a rule of thumb. It is a proof, and the pair table shows it.

The pair table, erased one line at a time

Run max_area on the six-wall input from before and record, for every cell, the step that retired it. A star marks the pair measured at that step:

height = [1, 5, 7, 2, 6, 3]      (* = measured at that step)
              j=1  j=2  j=3  j=4  j=5
              (5)  (7)  (2)  (6)  (3)
i=0 (1)         1    1    1    1    1*
i=1 (5)              3    3    3*   2*
i=2 (7)                   5*   4*   2
i=3 (2)                        4    2
i=4 (6)                             2

Each step erases one full row or column of what is left of the triangle, and the starred pair sits at its outer corner: the widest cell of that line. The last column of the table is the point. In every erased line, the largest area is the one just measured. Five steps erase 5 + 4 + 3 + 2 + 1 = 15 cells, which is every pair, and the answer, 15 at (1, 4), was measured at step 3.

The proof in plain words

Here is the sentence that stays true:

Invariant: before each iteration, every pair that uses a wall outside left..right holds at most best.

• At the start, left..right covers every wall, so there is nothing to check.
• Each step keeps it true. Say the code retires the left wall. It does that only when height[left] < height[right], so the area it just measured is height[left] × (right − left). The pairs that leave the range are (left, k) for every k from left + 1 to right. Each one's water is capped by height[left], and its width k − left is at most right − left. So each holds at most the area just measured, and best is at least that. Retiring the right wall (when height[right] <= height[left], ties included) is the mirror image.
• At the end, left == right, so every pair uses a wall outside the range. All of them hold at most best, and best is the area of a pair that was really measured. So best is the maximum. ∎

The proof used exactly two facts about the retired wall:

1. It caps the water. Paired with anything, the shorter wall allows a level of at most its own height.
2. Its remaining partners are all closer. Moving inward only shrinks the width.

Why not retire the taller wall? Fact 1 fails for it. A closer partner that is taller than the current short wall can lift the water, so the taller wall's row is not finished. A small failure is [1, 5, 5]. The correct code measures (0, 2) = 2, retires wall 0, then finds (1, 2) = 5. The swapped rule measures (0, 2) = 2, retires wall 2, measures (0, 1) = 1, and returns 2. On the LeetCode example it returns 8: it keeps the 1-high wall 0 to the end and throws away every wall that could have beaten it.

Ties. When the two heights are equal, both walls are finished. Each one's other partners are closer and capped at the same height. Moving either pointer is safe, and so is moving both at once. This code moves right on a tie; writing if height[left] <= height[right] moves left instead. Different tie rules visit different pairs and return the same answer.

Why "at most", not "less than"? The retired pairs include the pair just measured, and sooner or later the optimal pair itself, and those can equal best. Every other pair retired in a step is strictly narrower than the measured one, so it is strictly smaller as long as the short wall is taller than 0. A wall of height 0 holds 0 with every partner, so there even the narrower pairs tie.

🧠 Stronger than it needs to be. The proof shows only that best reaches the maximum. In fact, when the answer is positive, max_area measures every optimal pair. Take an optimal pair (i, j) with area OPT > 0, and look at the first step that retires i or j, say i. Then left == i and right >= j. If right were beyond j, the pair just measured would have water level height[i], which is at least the level of (i, j), and more width, so it would hold more than OPT. That is impossible. So right == j, and (i, j) itself was measured. Only when the answer is 0, as in [0, 0, 5], can an optimal pair go unmeasured, and then every pair ties at 0 anyway. A check of 197,650 inputs under both tie rules agreed.

Your turn: the proof never mentions water. Which of these scores can you still maximize with "measure, then retire the shorter wall"? Check each against the two facts before you look.

1. min(h[i], h[j]) × (j − i + 1), which counts lines instead of gaps
2. (h[i] + h[j]) × (j − i)
3. max(h[i], h[j]) × (j − i)

Break it on purpose

Each of these edits to max_area looks reasonable. Every result below comes from running the edited code on the LeetCode example, whose true answer is 49:

The first bug is the sneakiest because it passes some tests: on [4, 9] there is only one pair, so the last pair is also the best. Update best inside the loop, for the pair you just measured, on every iteration.

Edge cases

⚠️ Other languages. Python integers never overflow. In Java, C# or C++, check that the product fits. Here the largest possible area is 10⁴ × 99,999 = 999,990,000, which fits in a 32-bit int (the limit is 2,147,483,647). With larger limits you would need 64-bit arithmetic.

Test it against the slow version

The brute force earns its keep here. Small heights, 0 to 6, force plenty of ties and zeros, which is where pointer bugs hide:

import random

def check(solution, trials=3000):
    for _ in range(trials):
        n = random.randint(2, 9)
        height = [random.randint(0, 6) for _ in range(n)]
        got, want = solution(height), max_area_brute(height)
        assert got == want, (height, got, want)
    print("all matched")

check(max_area)

Success prints all matched. All four wrong edits in the table fail within a handful of trials, and the assertion message hands you a small failing input to trace by hand.

Your turn: a teammate says the loop wastes time measuring pairs that obviously lose, and submits this:

def max_area_skip(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        low = min(height[left], height[right])
        best = max(best, low * (right - left))
        while left < right and height[left] <= low:
            left += 1
        while left < right and height[right] <= low:
            right -= 1
    return best

Is it correct? What is its time complexity? How many areas does it compute on the LeetCode example?

Cousin, not twin: Trapping Rain Water

Predict first: now make the lines solid bars, each 1 unit wide, and pour rain over the whole skyline [1, 8, 6, 2, 5, 4, 8, 3, 7]. Is the trapped water 49 again?

This is LeetCode 42: Trapping Rain Water. Water above column i is

water[i] = min(tallest bar in 0..i, tallest bar in i..n−1) − height[i]

Both ranges include i itself, so the result is never negative.

The water sums to 19. A prefix-maximum array and a suffix-maximum array compute this table in O(n) time and O(n) space. Two pointers drop the arrays:

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        left_max = max(left_max, height[left])      # tallest in 0..left
        right_max = max(right_max, height[right])   # tallest in right..n-1
        if left_max < right_max:
            water += left_max - height[left]        # cell left is settled
            left += 1
        else:
            water += right_max - height[right]      # cell right is settled
            right -= 1
    return water

print(trap([1, 8, 6, 2, 5, 4, 8, 3, 7]))   # 19

Why it works. left_max is exactly the left bound for cell left. Its right bound is the tallest bar anywhere to its right, which is at least right_max. If left_max < right_max, the lower bound is left_max no matter what stands in between, so the water above left is settled at left_max − height[left]. Otherwise, the mirror argument settles cell right. Each step settles one cell. The cell where the pointers meet always holds a tallest bar, so it holds no water. That is O(n) time and O(1) extra space.

Both problems start at the ends and move the lower side inward, but for different reasons:

Your turn: for [3, 0, 2, 0, 4], what does max_area return, and what does trap return? Work both out by hand first.

Final round: no label on the problem

Real problems don't announce their technique. Check whether the two facts of the proof hold, and if they don't, look for another tool.

Challenge 1: fences at arbitrary positions

You get fence posts as (position, height) pairs in no particular order, for example [(9, 4), (0, 3), (5, 8), (12, 6), (2, 7)]. Positions are distinct. Stretch a tarp between two posts; it holds min(height) × (distance between their positions). Return the best amount.

1. Which technique applies?
2. What must change first, and which fact of the proof needs that change?
3. What does it cost?

def max_fence_area(posts):
    posts = sorted(posts)                 # by position
    left, right = 0, len(posts) - 1
    best = 0
    while left < right:
        (xl, hl), (xr, hr) = posts[left], posts[right]
        best = max(best, min(hl, hr) * (xr - xl))
        if hl < hr:
            left += 1
        else:
            right -= 1
    return best

print(max_fence_area([(9, 4), (0, 3), (5, 8), (12, 6), (2, 7)]))   # 60

Challenge 2: two sights and a walk

values = [8, 1, 5, 2, 6] rates sightseeing spots along a street. The score of spots i < j is values[i] + values[j] + i − j: two attractions, minus the walk between them. Return the best score. This is LeetCode 1014: Best Sightseeing Pair.

It is a pair problem with a distance in it. Is it this lesson's technique?

def max_score_sightseeing(values):
    best_left = values[0] + 0          # largest values[i] + i so far
    best = float("-inf")
    for j in range(1, len(values)):
        best = max(best, best_left + values[j] - j)   # j as the second spot
        best_left = max(best_left, values[j] + j)     # j as a future first spot
    return best

print(max_score_sightseeing([8, 1, 5, 2, 6]))   # 11

Quick-fire: which tool?

Name the technique for each one before you open the answer.

1. Buy on one day and sell on a later day; maximize the price difference.
2. Choose two lines; maximize min(height) × distance.
3. Rain falls on a skyline of unit-width bars; how much stays?
4. Find two values in a sorted array that add up to a target.

Cheat sheet

Before moving on, open a blank editor and solve LeetCode 11 from memory. Then explain it aloud: what the contract asks for, what the brute force wastes, what the invariant says before each iteration, why the shorter wall is finished but the taller one is not, and what goes wrong on [1, 5, 5] if you swap them. Finish with one score change that keeps the rule safe and one that breaks it.

Next: Sliding Window Patterns, where two pointers move in the same direction and keep state about everything between them. For the rest of the pointer family, including Two Sum II, 3Sum and fast/slow pointers, go back to Two Pointer Techniques.