Two Pointers: Throwing Work Away on Purpose

Most array problems have an obvious solution that looks at every pair: two nested loops, O(n²) comparisons, and an answer you can trust. The two-pointer technique is the habit of noticing when almost all of those pairs can be thrown away without ever being looked at.

It is not one algorithm. It is a shape that turns up in pair sums, palindromes, sliding windows, in-place rewrites, merging, and a handful of problems that look nothing like any of those until you see it. This section works through fourteen of them, and every one is the same three lines of bookkeeping with a different question in the middle.

The argument that makes it legal

Start with the problem the whole technique grew out of. Given a sorted array and a target, find the pairs that sum to it. Put one pointer on the smallest value and one on the largest, and look at what a single comparison tells you.

Say a[lo] + a[hi] comes out under the target. The tempting reading is that this particular pair is too small, so try another one. The useful reading is far stronger: a[hi] is the largest value left in the array, so it is the best partner a[lo] will ever be offered. If even that partner is not enough, a[lo] cannot reach the target with anything that remains. That is not one pair being rejected, it is one value being eliminated against every candidate at once.

The mirror image holds when the sum is over the target. a[lo] is the smallest value left, so a[hi] is too big for every partner still in play, and hi moves down.

That is the entire justification. Each comparison retires one value permanently, there are n values, so the pass makes at most n comparisons where the nested loops made about n²/2. Sorting first costs O(n log n), which is why nearly every problem in this section starts with a sort and still comes out ahead.

The template

Converging problems all compile down to this. Click a box to read what it is for, or play the trace to watch it run on a real array.

// The converging template. Everything in this section is a variation
// on the three branches in the middle.
function twoSumSorted(a, target) {
  const pairs = [];
  let lo = 0, hi = a.length - 1;

  while (lo < hi) {
    const sum = a[lo] + a[hi];

    if (sum === target) {
      pairs.push([a[lo], a[hi]]);
      lo++; hi--;
      // Step past duplicates so the same pair is not reported twice.
      while (lo < hi && a[lo] === a[lo - 1]) lo++;
      while (lo < hi && a[hi] === a[hi + 1]) hi--;
    } else if (sum < target) {
      lo++;   // a[lo] can never reach the target: a[hi] was its best partner.
    } else {
      hi--;   // a[hi] is too big for every partner still in play.
    }
  }
  return pairs;
}

Three shapes, and how to tell them apart

Every problem in this section is one of three arrangements. Recognising which one you are in is most of the work, because the shape decides what the pointers mean and what moving them costs.

1. Converging: one pointer at each end

The pointers start apart and walk towards each other, and the loop ends when they meet. Reach for it when a pair is measured by something that grows as you move one way and shrinks as you move the other: a sum over sorted values, an area bounded by two walls, characters compared across a midpoint.

Total pointer movement is exactly n, so the pass is O(n). That is the next page.

2. Same direction: a fast pointer and a slow one

Both start at the front. The fast one scans while the slow one trails behind marking something: the end of the region already written, or the left edge of a window. The loop looks nested, because the slow pointer often moves several times inside one iteration of the fast one, but both only ever move forward, so between them they make at most 2n moves. That is where sliding windows and in-place rewrites come from, and it is the third page.

3. One pointer per sequence

Two or three sorted arrays, one pointer in each, and a rule for which one advances. Merging is the familiar case; finding the values common to three arrays, matching officers to thieves, and even the celebrity problem are the same idea wearing different clothes. That is the last page.

What the technique buys, and what it costs

The gain is not only asymptotic. A two-pointer pass reads memory in order, allocates nothing, and holds two integers of state, so it often beats a hash-map solution of the same complexity on real inputs even where the theory says they tie.

The cost is a specific kind of fragility. A hash-map Two Sum works on any array. The two-pointer version returns confident nonsense on an unsorted one, because the elimination argument it rests on is simply not true there. Whenever you reach for this technique, be able to say out loud which ordering makes your comparison monotone. If you cannot, it does not apply yet.

Check yourself

Next: walking in from both ends, where the converging shape handles pair sums, palindromes and the container problem.