Two Pointers
The two pointers technique uses two indices that walk through a sequence, often from opposite ends or at different speeds. It replaces nested loops with a single coordinated pass.
Opposite ends
A common pattern on a sorted array is finding two values that sum to a target. Place one pointer at the left and one at the right:
- If the sum is too small, move the left pointer rightward to increase it.
- If the sum is too large, move the right pointer leftward to decrease it.
- If they meet, no pair exists.
Each pointer only moves inward, so the whole scan is linear instead of quadratic.
Same direction
Pointers can also chase each other in the same direction, such as a slow pointer building a clean result while a fast pointer reads ahead. This handles tasks like removing duplicates in place.
When it fits
Two pointers shine when the data is ordered or when a condition lets you safely advance one side without missing answers.
Key idea
Coordinating two moving indices turns many nested loops into a single linear scan.