Container With Most Water
Discover what you can safely leave behind.
The challenge, in plain language +
A row of upright walls stands one unit apart. Each number gives a wall's height. Choose two walls to form the sides of a container; the floor lies between them. Water can rise only as high as the shorter chosen wall. Return the largest cross-sectional area any pair can hold. Use nonnegative finite heights; with fewer than two walls, return 0.
Which fact makes it possible to eliminate many pairs at once?
This lesson uses 2D: exact positions, widths and comparisons are easier to read in one plane.
Why this approach works
Best stores the largest area evaluated so far. Every pair removed by discarding a shorter boundary wall has area no larger than an area already evaluated; any pair that could improve best is still inside the remaining interval.
Every iteration moves exactly one endpoint inward, so there are at most n - 1 evaluated pairs. Updating the area and best takes constant work: O(n) time and O(1) extra space.
Common failure: Moving the taller wall because it looks promising. Keeping the shorter wall retains the height limit while reducing width.
A fresh solve is the test.
Loading your saved attempts…