Container With Most Water
Module 10 · Two Pointers
Problem
height[i] is the height of a vertical line at position i. Choose two
lines; together with the x-axis they form a container. Return the
maximum water area — (distance between lines) × (shorter line's height).
Examples
Example 1
Input
height = [1,8,6,2,5,4,8,3,7]Output49 (lines at 1 and 8: width 7 × min(8,7))Example 2
Input
height = [1,1]Output1Constraints
2 ≤ n ≤ 10⁵ · heights in [0, 10⁴].
Attempt it first
The most famous elimination argument in interviewing — and the converging lesson warned you about it: the pointer rule ("move the shorter one") is easy to guess and hard to prove, and interviewers push on the proof. The input is NOT sorted this time, so the lesson's sortedness argument doesn't transfer directly — something else must justify elimination. Find the rule, then find the reason.