Two Pointers

Here is a small puzzle. You have a list of numbers, sorted smallest to largest, and a target:

const values = [2, 5, 8, 12, 17, 23, 30];
const target = 20;

Find the two numbers that add up to 20. (It is 8 and 12.)

First, the obvious way

Try every pair. For each number, check it against every other number:

function twoSum(values: number[], target: number) {
  for (let i = 0; i < values.length; i++) {
    for (let j = i + 1; j < values.length; j++) {
      if (values[i] + values[j] === target) return [i, j];
    }
  }
  return null;
}

This works. Read it and convince yourself before moving on — the outer loop picks the first number, the inner loop tries every number after it as a partner.

The problem is how much work it does. With 7 numbers there are 21 pairs. With 1,000 numbers there are about half a million. With a million numbers there are five hundred billion, and your program never finishes.

Now use the fact that it is sorted

The brute-force version never uses the ordering. It would behave identically on a shuffled list. That is a clue that we are leaving something on the table.

Put one finger on the smallest number and one on the largest. Add them.

• Too small? The only way to get a bigger sum is to move the left finger right.
• Too big? The only way to get a smaller sum is to move the right finger left.
• Exactly right? Done.

Step through it — watch which cells go grey, and read the sentence underneath each step:

while (low < high) {  const sum = values[low] + values[high];   if (sum === target) return [low, high];  if (sum < target) low += 1;   // need a bigger sum  else high -= 1;               // need a smaller sum}

Each move throws away a pointer’s worth of possibilities and we never go back. That is one pass — $O(n)$ — instead of half a million.

The part that is easy to skip past

It is worth being precise about why moving a pointer is allowed, because this is the actual idea and everything else is bookkeeping.

Suppose values[low] + values[high] is too small. We move low right. But that discards every remaining pair involving values[low] — not just this one. Is that safe?

Yes, and here is the argument. values[high] is the largest value left. So pairing values[low] with anything else still in range gives a smaller sum than the one we just computed — and that one was already too small. No pair containing values[low] can reach the target, so throwing them all away loses nothing.

The mirror image holds when the sum is too big: values[low] is the smallest value left, so nothing can pair with values[high] to come down far enough.

The code

function twoSum(values: readonly number[], target: number): [number, number] | null {
  let low = 0;
  let high = values.length - 1;

  while (low < high) {
    const sum = values[low]! + values[high]!;
    if (sum === target) return [low, high];
    if (sum < target) low += 1;    // need a bigger sum
    else high -= 1;                // need a smaller sum
  }

  return null;                     // pointers met, nothing found
}

Compare it to the brute-force version at the top. Same problem, one loop instead of two, and the only new idea is the three-way comparison in the middle.

When you cannot sort

Two pointers needs sorted input. If your data is not sorted and sorting would lose information you need — the original positions, say — reach for a hash map instead. It solves the same problem in one pass with no ordering requirement, by trading memory for it.

The same idea, three shapes

Two pointers is a family rather than one loop. What changes is where the pointers start and what moves them:

Opposite ends, moving toward each other — what we just did. Pair sums, checking whether a word is a palindrome, the container-with-most-water problem. The gap shrinks every step, so it always finishes.

Both at the start, one faster — used on linked lists to find the middle in one pass, or to detect a loop. Move one pointer two steps for every one step of the other.

Both at the start, one lagging behind a condition — that is a sliding window, and it gets its own article because the bookkeeping is different enough to be worth separating.