Algorithms / Two Pointers Sorted Pairs
Least You Need to Know: Opposite-End Two Pointers and Sorted Pair Search
When data order lets you predict how a sum or comparison changes, two pointers can eliminate large parts of the search space without backtracking. This is the interview reason sorted-pair, palindrome, and container-style problems collapse from quadratic scanning to linear passes.
Least you need to know
- Opposite-end two pointers rely on a monotone effect when one pointer moves.
- In a sorted array, moving the left pointer increases the sum and moving the right pointer decreases it.
- Once a pair is too small or too large, many other pairs can be ruled out immediately.
- Pointer movement rules must match the invariant; random movement destroys the proof.
- Duplicate handling usually happens only after a valid pair or kept value is chosen.
Key notation
- l, r — left and right pointers scanning from opposite ends
- sorted order — monotone order that makes pointer moves predictable
- invariant — fact preserved after every pointer update
Worked example
- In a sorted array, compare
a[l] + a[r]to the target. - If the sum is too small, moving
lright is the only move that can increase it. - If the sum is too large, moving
rleft is the only move that can decrease it. - That monotone reasoning is why one pass is enough.
Common mistakes
- Students often use two pointers on unsorted data where pointer moves have no predictable effect.
- Students often move both pointers when only one move is justified by the invariant.
- Students often forget to skip duplicates only after recording a kept answer.
How to recognize it
- The prompt mentions a sorted array, sorted string, or comparison from both ends.
- A left move and a right move change the score in opposite directions.
- A brute-force nested scan would revisit many dominated pairs.
Next recommended lesson
Continue through this topic with Least You Need to Know: Union-Find for Connectivity and Cycles.
Least You Need to Know: Union-Find for Connectivity and CyclesRelated lessons
Keep going with nearby lessons in the same topic.