Container With Most Water
Container With Most Water is a medium Two Pointers problem from the Blind 75. The key pattern is two pointers, and a good solution runs in O(n) time.
Problem
Choose two vertical lines and return the largest rectangular water area they can contain.
Examples
Example 1
Input
[2,9,3,7,4,8]Output
32Example 2
Input
[1,1]Output
1Example 3
Input
[3,1,6,4,5,2,7]Output
24Approach
Start with the widest pair and always move the shorter line inward. Moving the taller line can never give a larger area, because the height is capped by the shorter one.
| Pattern | Two pointers |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Area is min(height) × distance between indices, not the sum of heights.