Two pointers

The problem it solves

“Find two numbers in this array that sum to a target.” The obvious answer checks every pair: n²/2 combinations, quadratic, done. The interviewer’s follow-up — “the array is sorted; can you do better?” — is the door into one of the highest-frequency patterns in all of interviewing. Two pointers turns pair-finding over sorted data from O(n²) into a single O(n) walk, with O(1) space, and the same shape solves container-with-most-water, 3Sum (as the inner loop), palindrome checks, and sorted-array merging.

The pattern’s real product isn’t the answer — it’s the elimination proof. Each step doesn’t just fail to find a pair; it proves an entire element can never participate in any answer, permanently. Understanding why that proof holds is understanding the pattern; everything else is typing.

The intuition — and where it breaks down

Two people searching a bookshelf sorted by price for two books that together cost exactly $50. One starts at the cheapest end, one at the priciest. They price their current pair: $8 + $47 = $55 — too much. Who moves? The expensive-end person steps inward, and here is the entire argument for why that’s safe: the $47 book was just tested against the cheapest book in play. If $47 fails even with the cheapest available partner because the total is too high, no other partner can save it — every alternative costs more than $8. The $47 book is out, forever, against everyone. Symmetrically, when the sum is too low, the cheap book has just failed with the richest available partner, and it retires.

One test, one permanent elimination. That’s why the walk is linear: n elements, and each step retires exactly one.

Where the analogy breaks: it only works because the shelf is sorted — “cheapest available partner” must actually be at the end the pointer sits on. On unsorted data the elimination argument evaporates and the pattern silently returns wrong answers, not errors. Also, the shelf story suggests both people might move together; they never do. Exactly one pointer moves per step, chosen by the comparison — moving both skips pairs unexamined.

Loading…

A walkthrough you can check

Find a pair summing to 12 in [1, 3, 5, 8, 9, 11].

1. left = 0, right = 5: 1 + 11 = 12 — found immediately? Only if you’re lucky. Let’s make it 14 instead.
2. Target 14: 1 + 11 = 12, too small → 1 retires (it just failed with the largest partner alive). left = 1.
3. 3 + 11 = 14 — found, two comparisons, four elements never touched.

Now target 100 on the same array: every step’s sum is too small, left marches rightward retiring 1, 3, 5, 8, 9 in turn, the pointers meet, and the answer is a proven “no such pair” — six elements, five eliminations, done. The visualization’s seeded inputs include these exhaustion runs deliberately (about one seed in five), because the failure walk is where the correctness argument is most visible: every rejection is annotated with which partner the element failed against.

The invariant

Every pair with at least one member outside [left, right] has been proven unable to hit the target. The window shrinks only by adding such proofs, so when it empties, all pairs are refuted. That phrasing survives generalization better than “move the pointer on the small side”: in container-with-most-water the eliminated thing is “this wall can never bound a bigger container”; in a palindrome check it’s “these two characters matched, so the answer now depends only on the interior”. Same skeleton — a window whose exterior is settled — different predicate.

The step-count corollary: each iteration moves exactly one pointer exactly one place inward, so there are at most n − 1 iterations. The trace enforces this as a test: comparisons ≤ n − 1, always.

Complexity, derived

Time O(n) by the counting above — but the honest ledger includes what sortedness cost. If the input arrived unsorted, sorting first is O(n log n), and then the hash-map alternative deserves the comparison it always gets in interviews: map: O(n) time, O(n) space, no sort needed, returns original indices. Two pointers: O(n) time after sorting, O(1) space, returns value-ordered positions. Neither dominates; which one the problem wants depends on whether input is pre-sorted, whether indices matter, and whether O(n) extra memory is acceptable. Saying that trade-off out loud is the interview answer.

Space is O(1) — two integers — which is the pattern’s enduring edge and the reason it stays relevant even where the map is simpler.

What people get wrong

Running it on unsorted input. The most dangerous failure mode in this whole catalog, because nothing crashes — the elimination proofs are just false, and the “no pair exists” verdict is unearned. Sorted input is a precondition, not an optimization.

left <= right instead of left < right. Equality pairs an element with itself; a[3] + a[3] hitting the target is not a pair. One character, silent wrong answers on specific inputs.

Moving both pointers on a miss. Feels symmetric, skips real pairs. Only the proven-useless element retires, and only one element per step earns that proof.

Conflating the two two-pointer families. Opposite-ends (this page) solves pair/symmetry problems. Same-direction slow/fast solves deduplication, cycle detection, and sliding windows. They share a name and almost nothing else; answering a slow/fast question with an opposite-ends setup is a category error interviewers see weekly.

Finding one pair when the problem asked for all. “All pairs” requires continuing past a hit — advance both pointers, and skip duplicate values on both sides to avoid emitting the same value-pair twice. This is exactly the inner loop of 3Sum, where most 3Sum bugs actually live.

Implementation notes across languages

The pattern is index arithmetic and portable, so the notes are about ecosystems. In Python, resist the urge to slice — a[left:right] copies and turns O(n) into O(n²); keep integer indices. In JavaScript, the same warning applies to slice/shift habits. Java/C++ implementations are naturally clean; the only trap is signed overflow in a[left] + a[right] for extreme values (use long in Java when values approach the int boundary). Cross-language, the interview-ready formulation returns indices into the sorted order — if the problem wants original indices, either the map approach or a sort of (value, original-index) pairs is the answer, and noticing that requirement early is worth more than fast typing.