Container With Most Water
Medium · rating 1500 · Two Pointers
The first line has n. The second line has n non-negative integers, vertical line heights. Choosing two lines, the water they hold is min(height) × distance. Print the maximum.
Constraints: 2 ≤ n ≤ 105
Editorial
Approach
Two pointers at the ends. The area is limited by the shorter line, so move that pointer inward — keeping the taller line and hoping for a taller partner. Track the best area as the pointers converge.
Why moving the shorter side is right
Moving the taller line can only lower or match the height while shrinking the width, so it can never beat the current area; only the shorter line has upside.
i, j, best = 0, n-1, 0
while i < j:
best = max(best, min(h[i], h[j]) * (j - i))
if h[i] < h[j]: i += 1
else: j -= 1Complexity
Time: O(n). Space: O(1).
Related problems
- Minimum Size Subarray Sum — Medium
- Subarrays With Product Below K — Medium
- Subarray With Target Sum — Medium
- Sort Colors — Medium
- Two Sum (Sorted) — Medium
- Count Distinct (Sorted) — Medium