Two pointers
Two indices that move toward each other (or together) so each step safely discards part of the search.
Container With Most Water. height[i] is a vertical wall at x = i. Choose two walls that, with the x-axis, hold the most water. Return the area.
Signals that point here
- The input is sorted, or sorting it is cheap and does not lose the answer.
- Pairs or triplets with a sum condition (
2Sumon sorted input,3Sum). - In-place rewrites: remove duplicates, move zeros, partition (Dutch flag).
- Palindromes and "compare from both ends".
The idea
Start with the widest container. Width can only shrink from here, so the only way to do better is a taller short wall. Moving the taller wall inward can never raise the minimum, so every container it would form is no better: discard them by moving the shorter wall.
That argument is the whole pattern: each move must be justified by a sentence that says why the discarded options cannot win. Say it out loud; it is what separates a pattern-matcher from someone who understands the proof.
def max_area(height: list[int]) -> int:
left, right, best = 0, len(height) - 1, 0
while left < right:
width = right - left
best = max(best, width * min(height[left], height[right]))
if height[left] < height[right]:
left += 1 # the short wall limits every narrower box
else:
right -= 1
return bestpublic static class TwoPointers
{
public static int MaxArea(int[] height)
{
int left = 0, right = height.Length - 1, best = 0;
while (left < right)
{
int width = right - left;
best = Math.Max(best, width * Math.Min(height[left], height[right]));
if (height[left] < height[right]) left++; // short wall limits every narrower box
else right--;
}
return best;
}
}Complexity
O(n) time, O(1) space: each step moves one pointer, and they meet after n - 1 steps.
Pitfalls interviewers watch for
- Moving the taller wall ("it feels like progress").
- Off-by-one in width: it is
right - left, not+ 1. - For 3Sum: forgetting to skip duplicate values after a match, which returns duplicate triplets.
Variants worth knowing
- Same direction (fast/slow writer): remove duplicates from a sorted array in place.
- 3Sum: fix
i, then two pointers on the rest;O(n²). - Trapping Rain Water: two pointers carrying
left_maxandright_max.
Test it like the interviewer will
max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])returns49max_area([1, 1])returns1max_area([4, 3, 2, 1, 4])returns16max_area([1, 2, 1])returns2- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Given a sorted array, return whether any two numbers sum to
kinO(1)extra space. - Return all unique triplets that sum to zero.
- Move all zeros to the end of an array in place, keeping the order of the other elements.
Check yourself
Why is it safe to move the shorter wall?
Every narrower container that keeps the shorter wall has a smaller width and a height capped by that same wall, so none can beat the current one.
What usually has to be true of the input for opposite-end pointers?
Sorted order (or a monotone property) so a comparison tells you which side to discard.