Two Pointers

The 10-second versionCopy Anchor Link

Two pointers is what you reach for the moment you notice a nested loop redoing the same work. Instead of pinning one element and scanning everything after it, you keep two indices and move them on purpose — toward each other from the ends, or both forward at different speeds. When the data carries order (a sorted array, a palindrome, a partition), each move proves that a whole block of answers is impossible, so you throw it away in one step. Two indices, one pass: O(n) where the double loop cost O(n²).

Why this existedCopy Anchor Link

Two pointers has no single birthday — it's a folk technique that fell out of sorting, because sorting is where the pattern first paid rent. Sorting an array is only worth anything if you can then walk it cheaply, and the walk is always done by two indices reading the same block of memory in lockstep.

• 1945 — John von Neumann describes merge sort for the EDVAC. The heart of it is the merge: two pointers, one per sorted run, advancing whichever head is smaller. Two pointers is the merge.
• 1961 — Tony Hoare publishes Quicksort. Its partition step sends one pointer up from the left and another down from the right, swapping until they cross. Two pointers again, this time converging.
• 1976 — Edsger Dijkstra poses the Dutch national flag problem in A Discipline of Programming: sort 0s, 1s and 2s in one pass using three pointers (low, mid, high). The same idea, one index wider.

Why it mattered then: divide-and-conquer sorts like merge sort promise O(n log n), but that promise is only kept if the combine step is linear. If merging two halves cost O(n²), the whole sort would collapse. Two pointers is precisely the trick that keeps the combine step cheap — so half of sorting theory quietly depends on it.

Inside the inventor's headCopy Anchor Link

Forget the name for a second and look at the problem pattern that forces the trick: you're given a sorted array and asked for two numbers that add up to a target (the classic two-sum). The honest first attempt is unforgiving:

// the honest brute force: check every pair — O(n^2)function twoSumNaive(a, target) {  for (let i = 0; i < a.length; i++)    for (let j = i + 1; j < a.length; j++)      if (a[i] + a[j] === target) return [i, j];  return null;}

You can picture the work as a triangular grid of every pair. The brute force checks cells one by one, row after row. The question that unlocks everything is: "Is there something about sorted order that lets me cross out an entire row or column at once?"

Here's the trap. Your instinct is to fix the smaller index i, then binary-search for the partner — that's O(n log n), better, but you paid for the sort and now you're doing independent searches that never share information. The real pivot is to make the two indices cooperate instead of scanning separately. Start one at each end and let the sum itself tell you which index to move.

That is the "aha": because the array is sorted, one comparison is a proof about many pairs. a[lo] paired with a[hi] (its largest possible partner) is too small — therefore a[lo] can't pair with anything, and its entire row can be discarded. One comparison, one row gone.

The same move wears different costumes, and recognizing the costume is the skill:

• Palindrome check — pointers at both ends, compare, step inward.
• Remove duplicates in place — a slow write-pointer and a fast read-pointer.
• Partitioning — pointers converging while swapping elements to opposite sides.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

For the sorted two-sum, keep lo at the start and hi at the end. If the sum is too low, the smallest value has no partner, so advance lo. If it's too high, the largest value has no partner, so retreat hi. Equal means done.

The invariantCopy Anchor Link

Everything hangs on this one loop invariant, and it has to survive every iteration:

• Resolved-outside. No valid pair uses an index outside [lo, hi]. Any index we've walked past is provably useless — it can't pair with anything still inside the window.
• Untouched-inside. The answer, if it exists, is fully contained in [lo, hi].
• Progress. Every iteration moves exactly one pointer, so hi - lo strictly shrinks and the loop terminates.

Because the two rules above hold before the first iteration and are restored after each, when lo meets hi with no match we know no pair exists — not just that we failed to find one.

A worked traceCopy Anchor Link

Two-sum on [1, 2, 3, 5, 8, 13] with target 11 (the answer is 3 + 8):

Five comparisons for six elements. The brute force would have checked up to 15 pairs.

It in codeCopy Anchor Link

// a is sorted ascending; returns the two indices or nullfunction twoSum(a, target) {  let lo = 0, hi = a.length - 1;  while (lo < hi) {    const sum = a[lo] + a[hi];    if (sum === target) return [lo, hi];    if (sum < target) lo++;   // a[lo] too small to pair with anyone    else hi--;                // a[hi] too big to pair with anyone  }  return null;}

The other flavour: same-direction (fast/slow) pointersCopy Anchor Link

Opposite-direction pointers solve matched problems. Same-direction pointers solve in-place rewriting problems — like deleting duplicates without allocating a new array.

// sorted array; keep one of each, return the new lengthfunction removeDuplicates(a) {  if (a.length === 0) return 0;  let slow = 0;  for (let fast = 1; fast < a.length; fast++)    if (a[fast] !== a[slow]) a[++slow] = a[fast];  return slow + 1;}

Here slow marks the end of the deduplicated prefix and fast reads ahead. The invariant: the first slow + 1 slots always hold the unique values seen so far, in order. fast never looks back, so it's still one linear pass.

CostCopy Anchor Link

Where you meet it todayCopy Anchor Link

• Merge sort and external sorting. Timsort, k-way merges, and database sort-merge joins all run the merge step with two (or k) pointers over sorted runs.
• Quicksort's partition. The in-place split that makes quicksort fast is converging pointers — the exact shape from Hoare's 1961 paper.
• Editors and validation. Reversing a string in place, checking a palindrome, and normalizing whitespace are all two-pointer passes.
• Interview staples. Container-with-most-water, 3-sum, and merging sorted lists are two pointers in disguise.

// merge two sorted arrays into one sorted arrayfunction merge(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);  while (i < a.length) out.push(a[i++]);  while (j < b.length) out.push(b[j++]);  return out;}

RecapCopy Anchor Link

• Two pointers replaces a nested loop with two indices moving deliberately — toward each other, or both forward at different speeds.
• It works when the data has order, because one comparison then eliminates a whole block of candidate answers.
• The invariant is the whole proof: nothing useful ever sits outside the window, and one pointer always moves, so you terminate in O(n).
• It costs O(1) extra space — no tables, no sets, just arithmetic.

Next up: Sliding Window — two pointers pointed at a contiguous range, with a running summary that never re-scans.