How do you solve the Container With Most Water problem using two pointers?
Start with pointers at both ends. The area is the shorter height times the distance. Move the pointer at the shorter line inward, because moving the taller one can never increase the area.
Explain it simply
You have vertical walls of different heights and you want to pour in the most water between two of them. Water level is limited by the shorter wall, and width is the gap between them.
Start with the widest pair. Now ask: how can the area ever grow? Width only shrinks as pointers move in, so the only hope is a taller short wall. If you move the taller wall inward, the short wall still limits you and the width is smaller, so the area cannot improve. Therefore move the shorter wall.
Example
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let best = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
best = Math.max(best, area);
if (height[left] < height[right]) left++;
else right--;
}
return best;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // Output: 49Complexity
Time O(n), space O(1).
What to say in the interview
"Brute force checks every pair in O(n squared). With two pointers I start at the ends and always move the pointer at the shorter line, since the shorter line limits the area and the width only shrinks. That gives O(n) time and O(1) space."
Common mistakes
- Moving the taller pointer. That can only keep or reduce the area.
- Using the sum of heights instead of the minimum.