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.
The 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
Tiny worked example
- In a sorted array, compare `a[l] + a[r]` to the target.
- If the sum is too small, moving `l` right is the only move that can increase it.
- If the sum is too large, moving `r` left 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 this kind of problem
- 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.