Two pointers
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
When it applies
Reach for two pointers when the input is sorted, or when the answer involves a pair or a window whose ends move monotonically. The test is whether you can argue that one end can be discarded for ever after a comparison. If you cannot make that argument, you probably want a hash map or a sort first.
Signals in the question: "sorted array", "pair that sums to", "closest", "remove duplicates in place", "partition", "palindrome".
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
lo, hi = 0, len(a) - 1
while lo < hi:
if condition(a[lo], a[hi]):
return (lo, hi)
elif too_small(a[lo], a[hi]):
lo += 1 # a[lo] can never be part of the answer
else:
hi -= 1 # a[hi] can never be part of the answerint lo = 0, hi = (int)a.size() - 1;
while (lo < hi) {
if (condition(a[lo], a[hi])) return {lo, hi};
if (tooSmall(a[lo], a[hi])) ++lo;
else --hi;
}int lo = 0, hi = a.length - 1;
while (lo < hi) {
if (condition(a[lo], a[hi])) return new int[]{lo, hi};
if (tooSmall(a[lo], a[hi])) lo++;
else hi--;
}let lo = 0, hi = a.length - 1;
while (lo < hi) {
if (condition(a[lo], a[hi])) return [lo, hi];
if (tooSmall(a[lo], a[hi])) lo++; // discard the left end
else hi--; // discard the right end
}let (mut lo, mut hi) = (0usize, a.len() - 1);
while lo < hi {
if condition(a[lo], a[hi]) { return Some((lo, hi)); }
if too_small(a[lo], a[hi]) { lo += 1 } else { hi -= 1 }
}go lo hi
| lo >= hi = Nothing
| condition l r = Just (lo, hi)
| tooSmall l r = go (lo + 1) hi
| otherwise = go lo (hi - 1)
where l = arr ! lo
r = arr ! hiProblems
Pair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Medium15 minTwo walls holding the most water
The input is not sorted, but one comparison still rules out an end for good: the shorter wall can never do better.
Open the problem → Medium20 minAll distinct triplets summing to zero
Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.