Two Pointers
Walk two indices toward each other to prune the search space linearly.
The idea
The two-pointers technique places two indices at meaningful positions — often the two ends of a sorted array — and moves them based on a comparison. Each move eliminates possibilities that can never improve the answer, so a quadratic search becomes linear.
Sorting (or an existing order) is what makes the pruning sound: if the current sum is too small, the only way to grow it is to move the left pointer right; if it is too big, move the right pointer left. Neither pointer ever needs to backtrack.
Two people search a sorted bookshelf for two books whose page counts add up to a number. One starts at the thinnest book, the other at the thickest. If the total is too high, the thick-side reader steps toward thinner books; if too low, the thin-side reader steps toward thicker ones.
When to reach for it
- The array is sorted (or can be sorted cheaply).
- You seek a pair/triplet meeting a sum or difference condition.
- You are partitioning, reversing, or de-duplicating in place.
Language-independent template
sort(arr) # if not already ordered
left, right = 0, n - 1
while left < right:
evaluate(arr[left], arr[right])
if too small: left += 1
elif too big: right -= 1
else: record answerComplexity — time O(n), space O(1) (plus O(n log n) if a sort is required first).
Common mistakes
- Applying it to an unsorted array without sorting first.
- Moving the wrong pointer, which skips the real answer.
- Off-by-one in the loop guard (
left < rightvsleft <= right).
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Ignore non-alphanumeric characters and test whether a string is a palindrome.
Return every unique triplet whose sum is zero.
Compute how much water is trapped between elevation bars.