Container With Most Water: Why the Two-Pointer Greedy Is Correct
3 views
"Given an array of heights, pick two lines that together with the x-axis hold the most water" is a classic coding interview problem. The area between lines i and j is min(height[i], height[j]) * (j - i). The brute force checks every pair in O(n^2). The expected answer is an O(n) two-pointer solution, and the interviewer will almost certainly ask you to prove it works.
The algorithm
Start with the widest container: left pointer at 0, right pointer at n - 1. Compute the area, then move the pointer at the shorter line inward. Repeat until the pointers meet.
def max_area(height):
lo, hi = 0, len(height) - 1
best = 0
while lo < hi:
h = min(height[lo], height[hi])
best = max(best, h * (hi - lo))
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return best
Time is O(n), space O(1).
Why moving the shorter line is safe
Suppose height[lo] < height[hi]. Any container that uses line lo with some other right boundary k < hi has width smaller than (hi - lo), and its height is at most height[lo], because the shorter line limits the water. So every such container is no larger than the one we just measured. Line lo can never be part of a better answer, so discarding it loses nothing. The symmetric argument applies when the right line is shorter. When both are equal, moving either one is fine, since neither can produce a larger container with a narrower width at the same limiting height.
Interviewers love this argument because it shows you are not just pattern matching "two pointers." State it in one or two sentences.
Walk through an example
For [1, 8, 6, 2, 5, 4, 8, 3, 7]: start with lines 0 and 8, area = 1 * 8 = 8. Move left (1 is shorter). Lines 1 and 8: min(8, 7) * 7 = 49. Move right (7 is shorter). Lines 1 and 7: 3 * 6 = 18. Continue; the best stays 49.
Small optimization
After moving a pointer, you can skip any lines that are not taller than the one you just left, because they cannot improve the height while the width shrinks. It does not change the O(n) bound but reduces work on some inputs, and mentioning it shows you understand the invariant.
Do not confuse it with Trapping Rain Water
In Trapping Rain Water, water sits on top of every bar and you sum it; here you choose only two lines and ignore everything between them. Interviewers sometimes ask the difference to check that you understand both.
Follow-ups
1. Return the indices of the best pair: store them when best updates.
2. What if lines have widths or the x-positions are not evenly spaced? Use the actual x-distance in the formula; the same greedy argument holds as long as positions are sorted.
3. Prove the brute force is unnecessary: the elimination argument above is the proof.
How to present it
Give the brute force, explain the area formula, introduce the two pointers, and then give the elimination proof before coding. A clear proof often matters more than the code itself.
If you know the solution but struggle to explain the proof under pressure, Linkjob AI (https://linkjob.ai) offers real-time help during job interviews and technical interviews, helping you keep your reasoning clear and confident.