Two Pointers
Move the shorter side
Why it matters
Capacity planning often asks for the best pair of boundaries among many candidates. Measuring every pair repeats work and becomes quadratic as the number of boundaries grows. For [1, 8, 6, 2, 5, 4, 8, 3, 7], find the maximum container area with constant extra memory without evaluating all 36 pairs.
Example
Container With Most Water
height[i] is a vertical line at x = i. Pick two lines so the axis-aligned bucket they form holds the most water. Return that area.
- Input
- height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
- Output
- 49
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Container With Most Water
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]→49
The baseline, Try every pair of lines, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
With [1, 8, 6, 2, 5, 4, 8, 3, 7], indexes 1 and 8 hold 7 × 7 = 49. Instead of measuring all 36 pairs, start at maximum width and discard the shorter boundary after each measurement.
For height = [1, 8, 6, 2, 5, 4, 8, 3, 7], the first and last lines give width 8 and level 1, so area 8. The left line is shorter. Any other pair using that height 1 is narrower and cannot beat 8, so discard it.
The new pair uses heights 8 and 7 at indexes 1 and 8: width 7, level 7, area 49. Now the right side is shorter, so only moving it could raise the level enough to offset lost width. Repeating that proof removes one boundary per step without missing a better pair.
Visual anchor
Container With Most Water
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.