Container With Most Water
Medium Opposite ends, move the shorter
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Vertical lines stand at each index with given heights. Pick two lines that, with the x-axis, hold the most water. Return that amount.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: choose two walls that trap the most water.
Why this works: water = width × shorter wall. Start widest. Moving the taller wall can only lose width without raising the shorter wall, so always move the shorter one.
Example: [1, 8, 6, 2, 5, 4, 8, 3, 7]
l=0 (1), r=8 (7): area 8 → move ll=1 (8), r=8 (7): area 49 (best) → move r… no wider pair beats 49
✦Hints open one at a time
↗Approach
Two pointers at the ends. Record the area, then move whichever side is shorter, because the shorter line limits every container that uses it with a smaller width.
</>Solution (Java)
class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1, best = 0;
while (l < r) {
int h = Math.min(height[l], height[r]);
best = Math.max(best, h * (r - l));
if (height[l] < height[r]) l++; // the shorter line is the bottleneck
else r--;
}
return best;
}
}!Common mistake
Moving the taller side, or moving both — you can skip the best pair.
- Time: O(n).
- Space: O(1).
