Topic 3 of 20
Two Pointers
Two indices moving through data to replace nested loops with a single pass.
The concept
The two-pointer technique keeps two indices into a sequence and moves them according to a rule, turning many O(n²) pair searches into a single O(n) pass. There are two main shapes. Opposite ends: one pointer starts at the left, one at the right, and they move toward each other (palindromes, pair sums in a sorted array, container problems). Same direction: a fast "reader" scans every element while a slow "writer" marks where the next kept element goes (removing duplicates, moving zeroes, partitioning).
Two pointers usually needs some kind of order. If the input is not sorted, sorting it first (O(n log n)) often unlocks the technique, which is exactly how 3Sum and 4Sum reduce to repeated Two Sum. The key interview skill is proving why moving a pointer can never skip the answer. Practise saying that argument out loud.
This topic also prepares you for Sliding Window (two same-direction pointers with a condition) and for the fast & slow pointers used on linked lists.
Patterns you will learn
- Opposite Ends
- Same Direction (Read/Write)
- Sort + Two Pointers
- Dutch National Flag
- Merge Two Sorted Sequences
Problems, in order
- 1Valid PalindromeEasy
The simplest opposite-ends scan, with character filtering.
Opposite EndsReported at: MetaAmazonMicrosoft+3 - 2
Allows one deletion, so you learn to branch once and re-check; a Meta favourite.
Opposite EndsReported at: MetaAmazonApple+4 - 3Reverse StringEasy
In-place swap from both ends; the building block for reversal tricks.
Opposite EndsReported at: AmazonMicrosoftMeta+3 - 4
Filling from the end avoids overwriting data; a standard in-place merge.
Merge from the BackReported at: MetaMicrosoftApple+5 - 5
Introduces the reader/writer pointer pair.
Same Direction (Read/Write)Reported at: MetaAmazonMicrosoft+6 - 6Move ZeroesEasy
Stable in-place partitioning with minimal writes.
Same Direction (Read/Write)Reported at: MetaMicrosoftAmazon+7 - 7Is SubsequenceEasy
Greedy matching with two pointers over two strings.
Same DirectionReported at: AmazonGoogleAdobe - 8
Largest values sit at the ends, so you fill the output from the back.
Opposite EndsReported at: MetaAmazonGoogle+2 - 9
Sorted input turns Two Sum into an O(1)-space two-pointer scan.
Opposite EndsReported at: AmazonGoogleApple+2 - 103SumMedium
Reduces k-sum to 2-sum and tests duplicate handling; asked constantly.
Sort + Two PointersReported at: AmazonMetaMicrosoft+14 - 113Sum ClosestMedium
Same skeleton as 3Sum but optimising a distance instead of matching.
Sort + Two PointersReported at: MetaAmazonGoogle+4 - 124SumMedium
Generalises the k-sum reduction and overflow awareness.
Sort + Two PointersReported at: AmazonMetaApple+5 - 13
The classic 'move the shorter side' proof; very frequently asked.
Opposite EndsReported at: AmazonMicrosoftMeta+6 - 14Sort ColorsMedium
Three-way partitioning in one pass; also the core of 3-way quicksort.
Dutch National FlagReported at: AmazonMicrosoftMeta+5 - 15
Generalises read/write pointers to 'keep at most k copies'.
Same Direction (Read/Write)Reported at: Adobe - 16Boats to Save PeopleMedium
Pairs the heaviest with the lightest; a greedy argument in two-pointer form.
Sort + Greedy PairingReported at: AmazonAppleMicrosoft+4 - 17
Reverse the whole string, then each word: an in-place classic.
Reversal TrickReported at: MicrosoftAppleGoogle+3 - 18
Two pointers plus counting with powers of two; a strong Medium.
- 19
- 20
The most famous two-pointer Hard; also solvable with prefix maxima or a stack.
Opposite EndsReported at: AmazonMetaMicrosoft+12