Container With Most Water · Compound Engineer

Two pointers · Opposite ends

Medium · O(n) time · O(1) space

Problem

You are given an integer array height of length n. Line i is a vertical line from (i, 0) up to (i, height[i]). Pick two lines. With the x-axis they form a container, and the container can't be tilted. Return the most water a container can hold.

Example 1 Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (lines 1 and 8: min(8, 7) × 7) Example 2 Input: height = [1, 1] Output: 1

Constraints 2 ≤ n ≤ 10^5 0 ≤ height[i] ≤ 10^4

What the problem asks for

Choose exactly two lines, at positions i < j. The lines in between do not matter.
The water rises to the shorter of the two lines. Anything higher would spill.
Return the largest amount over all pairs.

So one pair holds min(height[i], height[j]) × (j − i). Wide pairs help, and tall pairs help, but they pull against each other.

Start with the direct approach

Measure every pair with that formula and keep the largest.

The code

Time and space

Time: O(n²). There are n × (n − 1) / 2 pairs, which is about 5 × 10⁹ for n = 10⁵. Space: O(1).

Building the faster solution

All the time goes into measuring pairs. So the question is: which pairs can we skip without measuring them?

Start with the widest pair

The first and the last line form the widest pair, and every other pair is narrower. So another pair can only win by being taller. But a pair's height is capped by its shorter line, and that is the line to watch.

The shorter line can be dropped

Measure the pair, and call its shorter line lo and the other hi. Any other pair that uses lo has its partner closer than hi. That pair is narrower, and its height is still capped by lo. So it cannot hold more than the pair we just measured.

That means lo is finished. We measure the pair, drop the shorter line and move that pointer inward. On the example, the pair (0, 6) has heights 3 and 4, so line 0 is dropped.

Why not drop the taller line?

The shorter line would stay in the pair and still cap the height, while the pair gets narrower. We lose width for nothing, and we might throw away the best pair. Equal lines are safe either way, because the argument holds for both.

The solution

Put lo on the first line and hi on the last. Set best = 0.
Measure min(height[lo], height[hi]) × (hi − lo) and keep the larger of it and best.
height[lo] ≤ height[hi]⟶lo moves right
otherwise⟶hi moves left
When the pointers meet, return best.

Pick an input and press Play, or use the arrow keys.

Equal lines and other edge cases

When the two lines are equal, the code drops lo, which is safe. With [1, 1] there is one pair and the answer is 1. On [4, 3, 2, 1, 4] the very first pair is the best, 4 × 4 = 16, and the rest are only checked.

Why it works

We never skip the best pair. Each time a line is dropped, every pair we give up that includes it is narrower and capped by the same line, so it cannot beat the pair we just measured.
Every pair is covered. A pair is either measured, or it contains a dropped line. The pointers only stop when they meet, so no pair is left unaccounted for.
The loop ends. Each pass moves one pointer one step closer, so it stops after n − 1 passes.

Complexity

O(n)

Time. Here's why: the pointers start n − 1 apart and every pass moves one of them one step closer. That is at most n − 1 passes, each doing a fixed amount of work.

O(1)

Space. Two pointers and best. Nothing grows with the input.

What can be optimized

The big-O is already optimal. Any line can be part of the best pair, so every line must be read, and O(1) space is the least possible.
A small speed-up: after dropping a line, keep skipping lines that are not taller than it. A narrower pair with a line that is not taller cannot win, so we save those measurements. The worst case is still O(n).

Check your understanding

Checkpoint 1 · Predict: on [3, 9, 2, 5, 8, 8, 4] we just measured (1, 5), heights 9 and 8. Which pointer moves, and where to?

Answerhi moves, from 5 to 4. The right line (8) is the lower one, so it is dropped.

Checkpoint 2 · Why not move both pointers inward every time?

AnswerThe taller line may be part of the best pair. At (1, 6) moving both goes to (2, 5), which skips (1, 5), the pair with 32.

Checkpoint 3 · For [4, 3, 2, 1, 4], what is the answer and how many pairs does the code measure?

Answer16, from the first pair (0, 4). It measures 4 pairs: 16, 9, 4 and 1. That is n − 1, not all 10 pairs.

Interviewer follow-ups

Open one to see an answer you could say out loud.

"Convince me you never skip the best pair."

What they are checkingWhether you can prove the greedy step, or only repeat "move the shorter one".

A strong answerEach time I drop a line, every pair I give up that includes it is narrower and capped by that same shorter line, so it cannot beat the pair I just measured. I only skip pairs that cannot win, and the pointers stop only when they meet.

"Now the lines hold water between all of them, not just between two. How much water in total?"

What they are checkingWhether you can adapt the two-pointer idea. This is Trapping Rain Water.

A strong answerThe water above a position fills up to the lower of the tallest line on its left and the tallest on its right, minus its own height. Keep two pointers and the tallest line seen from each side, and always move the pointer whose side has the lower tallest line, because that side already decides its level. O(n) time, O(1) space.

"Heights go up to 10,000 and there can be 100,000 lines. Can the area overflow?"

What they are checkingWhether you check the largest value before you trust the code.

A strong answerThe biggest area is 10,000 × 99,999, about 10⁹. A 32-bit integer holds about 2.1 × 10⁹, so it fits, with little room. If the limits grew I would use a 64-bit number. In Python it does not matter.

Spot this pattern

The answer depends on a pair of positions, and trying all pairs is O(n²).
The value of a pair is limited by one of its two ends (a min).
Moving one end inward lets you discard it for good.

When it does not apply: if a pair's value is not capped by one of its ends (for example height[i] + height[j]), dropping an end proves nothing, and this argument fails.