Overview
Two-pointer technique uses left and right indices that move toward each other to solve array problems without nested loops.
Analogy
Two people walking from opposite ends of a bridge, meeting in the middle.
Step-by-step
- Sort the array if looking for pairs that sum to a target.
- l = 0, r = len-1.
- If arr[l]+arr[r] < target: move l right. If > target: move r left. If == target: found.
Visual
Sorted [1,3,5,7], target=8: (1+7=8)→found
Common mistakes
- Forgetting to sort first for sum-pair problems.
- Moving both pointers when only one needs to move.
Practice questions
- Find all pairs summing to target in a sorted array.
- Remove duplicates from a sorted array in-place.
Time
O(n) after O(n log n) sort