Two Pointers Pattern
Two indices walk a sorted (or paired) structure from different positions to converge on a target.
When to Use It
Sorted arrays/strings, pairs/triplets summing to a target, in-place deduplication, palindrome checks.
Classic example: Two Sum on a sorted array; 3Sum.
How It Works
Two pointers collapses an O(n^2) pair search into O(n) by exploiting structure, usually sortedness, to prune one side of the search space per comparison. The pointers typically start at opposite ends and converge, but the converging-vs-same-direction distinction is important: opposite-end works for 'find a pair with sum X' on sorted data; same-direction (lead/follow) works for in-place compaction and removal.
The technique generalizes from pairs to triplets by fixing one element and running two pointers on the remaining range, that's how 3Sum drops from O(n^3) to O(n^2). When sorting is required first, total cost becomes O(n log n) but is still dominated by the sort, not the scan.
The pattern is conceptually distinct from sliding window even though both use two indices: sliding window maintains an aggregate over a contiguous range; two pointers makes a discrete decision (move left, move right, or record an answer) at each step based on comparing the endpoints.
Key Insight
When the array is sorted, comparing the endpoints tells you which pointer to move: moving the wrong one can only worsen the invariant, so the choice is forced and each pointer advances monotonically for O(n) total work.
Worked Example
Two Sum on a sorted array
nums = [1, 3, 4, 6, 8, 11], target = 10
- l=0, r=5: 1 + 11 = 12, too big, so move r left (11 can't pair with anything larger than 1)
- l=0, r=4: 1 + 8 = 9, too small, so move l right (1 can't pair with anything smaller than 8)
- l=1, r=4: 3 + 8 = 11, too big, so move r left
- l=1, r=3: 3 + 6 = 9, too small, so move l right
- l=2, r=3: 4 + 6 = 10, match
Result: Indices 2 and 3. Five comparisons, where checking every pair would take up to fifteen.
Templates
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
// record / return
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}left, right = 0, n - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
# record / return
left += 1
right -= 1
elif s < target:
left += 1
else:
right -= 1Common Pitfalls
- Forgetting to skip duplicates after a match in 3Sum-style problems, producing duplicate triplets in the output.
- Forgetting the array must be sorted; running two pointers on unsorted data silently produces wrong answers without crashing.
- Off-by-one in the loop bound: using i < n instead of i < n-2 for triplet outer loops, causing index-out-of-bounds.
- Mixing up converging vs same-direction patterns and moving both pointers when only one should advance.
- In palindrome checks, advancing both pointers before comparing rather than comparing then advancing.
When It Breaks
- Converging pointers need sorted input. If the input is unsorted and you must return original indices, sorting loses them: use a hash map (classic Two Sum) or sort (value, index) pairs.
- Each move must discard only answers that can't work. That guarantee comes from the ordering; without it (an unsorted array, or a target that isn't monotonic in the pointers), moving a pointer can skip the real answer.
- Counting pairs with duplicates needs care: when the values at both ends are equal, or a run of equal values matches, count the combinations before moving instead of stepping one at a time.
Variations
- Opposite-end converging: 2Sum sorted, container with most water, valid palindrome.
- Same-direction lead/follow: remove duplicates in-place, move zeroes, partition by predicate.
- Fixed-pivot + two pointers: 3Sum, 3Sum closest, 4Sum (nested fix-then-scan).
- Two arrays simultaneously: merge sorted arrays, intersection of two arrays.
Big O
- Time
- O(n)
- Space
- O(1)