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
Move the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Easy10 minPair 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 → Easy12 minCount the pairs whose sum is below a target
Sort it and start at both ends, and whenever the sum's small enough you'll have found a whole run of pairs in one go.
Open the problem → Easy10 minA palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minDoes the digit-square sequence reach 1
Replace n by the sum of the squares of its digits, again and again. Either you hit 1 or you go round a loop, and a fast and a slow pointer tell you which without storing anything.
Open the problem → Easy12 minA palindrome after deleting at most one letter
Walk in from both ends. At the first mismatch one of the two letters has to go, so you try both and the rest has to match exactly.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minSquares of a sorted array, in order
Negative numbers put the largest squares at both ends. Compare the ends and fill the result from the back.
Open the problem → Easy10 minIs one string a subsequence of another
One pointer on each string. You match the next letter of s as early as you can in t, and taking the earliest match never costs you anything.
Open the problem → Easy12 minTwo strings equal after their backspaces
A # deletes the letter before it. Read both strings from the back, where you already know which letters survive, and compare as you go.
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 → Medium20 minThe repeated number, without changing the array
Read the array as a list where index i points to nums[i]. The repeated value is where two arrows meet, which is the start of a cycle, and Floyd finds it in O(1) space.
Open the problem → Medium15 minKeep each value at most twice
A reader and a writer, and one comparison: a value may be written only if it differs from the value written two places back.
Open the problem → Medium20 minThe triple sum closest to a target
Fix the smallest of the three, then walk two pointers over the rest, moving whichever brings the sum towards the target.
Open the problem → Medium15 minCount the triplets with a sum below a target
Sort, fix the smallest value, and when the pair sum fits you've found a whole run of triplets in one step. There are no duplicates to worry about this time.
Open the problem → Medium15 minCount the triangles you can make
Sort, fix the longest side, and one scan counts every pair that works with it, several at a time.
Open the problem → Medium15 minWhere a linked list loops back on itself
A list starts at node 0 and might end or might loop. Floyd's two phases tell you which, and where the loop starts, in O(1) space.
Open the problem → Medium15 minThe smallest difference between two arrays
Sort both arrays and walk a pointer along each, always moving the one that's behind. It's the merge step with a running minimum.
Open the problem → Medium15 minSort three colours in one pass
Three regions grow from the two ends and the middle: zeros on the left, twos on the right, and an unread middle that shrinks with every step.
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 quadruplets with a given sum
3-sum with one more loop on the outside. Two values fixed, a pair scan for the rest, and the duplicates skipped at all three levels.
Open the problem → Medium15 minFewest boats under a weight limit
Sort, then try to pair the heaviest person left with the lightest. If even the lightest does not fit, the heaviest goes alone.
Open the problem → Medium20 minSubsequences whose smallest and largest fit a target
Sort, and once the smallest and largest of a range fit the target, every subset of what's between them fits too. That's a power of two in one step.
Open the problem → Medium15 minThe shortest part to sort so the whole array is sorted
Walk left to right keeping the running maximum to find where the bad part ends, then right to left with the running minimum to find where it starts.
Open the problem → Medium20 minThe next permutation, in place
Find the last place the array goes up, swap in the next bigger value from the right, and reverse what's after it with two pointers.
Open the problem → Hard25 minRain water trapped between walls
The water over a column is set by the lower of the tallest walls on its two sides. Two pointers know one of those for certain at every step.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.