Two Pointers
Two indices walk a sorted (or paired) structure from different positions to converge on a target.
Sorted arrays/strings, pairs/triplets summing to a target, in-place deduplication, palindrome checks.
Pointers advance monotonically toward (or with) each other, so combined steps are bounded by n. No auxiliary structure is needed beyond a couple of indices.
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.
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.
- 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.
- 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.
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--;
}
}Problems using this pattern
10Easiest first · Blind 75 above NeetCode 150