Two Sequences, One Pass Each

So far both pointers have lived in the same array. Give each one its own sequence and the technique carries over unchanged: at every step, look at what the pointers are reading, work out which one is behind, and advance that one. The pointer you leave alone is the one that still has something to offer.

Merge sort already uses this - its merge step is exactly two pointers over two sorted arrays. This page takes the same shape somewhere less obvious, ending with a problem that has no arrays in it at all.

Closest pair from two arrays

Two sorted arrays and a target. Pick one value from each so their sum is as close to the target as possible. The nested loops are O(n × m); the trick is choosing the directions.

Walk the first array upward from its smallest value and the second downward from its largest. Now the sum behaves exactly like the sorted Two Sum pass: advancing in the first array can only raise it, retreating in the second can only lower it. A sum under the target means the current value from the first array is as good as it will get against that partner, so move up; over the target means the partner from the second array is too large, so move down.

Both pointers move strictly towards each other in their own arrays, so the pass is O(n + m). Start them both at the front and the same code silently stops working: the two moves would then push the sum in the same direction, and there would be no rule for which pointer to advance.

// a ascending from the left, b descending from the right.
function closestPair(a, b, target) {
  let i = 0, j = b.length - 1;
  let best = Infinity, bestPair = null;

  while (i < a.length && j >= 0) {
    const sum = a[i] + b[j];
    if (Math.abs(sum - target) < best) {
      best = Math.abs(sum - target);
      bestPair = [a[i], b[j]];
    }

    if (sum === target) break;    // cannot do better than exact
    if (sum < target) i++;        // need a bigger value from a
    else j--;                     // need a smaller value from b
  }
  return bestPair;
}

Values common to three arrays

Three sorted arrays; report the values present in all three. Three pointers, all starting at the front, and one rule: if the three values are not equal, advance whichever pointer reads the smallest one.

The justification is the same elimination as always. The smallest of the three cannot appear later in the other two arrays, because those pointers are already sitting on something bigger and their arrays only grow from here. So that value can never be part of a common triple, and skipping it loses nothing.

On a hit, all three pointers advance past the matched value rather than by one, which is what stops a value repeated in all three arrays being reported several times. Total work is O(n + m + p), since every step retires at least one element for good.

function commonInThree(a, b, c) {
  const out = [];
  let i = 0, j = 0, k = 0;

  while (i < a.length && j < b.length && k < c.length) {
    if (a[i] === b[j] && b[j] === c[k]) {
      out.push(a[i]);
      const v = a[i];
      // Past the value, not just by one, so repeats are not re-reported.
      while (i < a.length && a[i] === v) i++;
      while (j < b.length && b[j] === v) j++;
      while (k < c.length && c[k] === v) k++;
      continue;
    }

    // The smallest cannot appear later in the other two arrays.
    const min = Math.min(a[i], b[j], c[k]);
    if (a[i] === min) i++;
    else if (b[j] === min) j++;
    else k++;
  }
  return out;
}

Policemen catch thieves

A street of cells, each holding an officer, a thief, or nothing. An officer can arrest one thief at most k cells away, and each thief can be arrested once. Maximise the arrests.

Collect the officer positions and the thief positions into two lists - both already ascending - and walk them with one pointer each. If the two in front are within k, pair them. If not, whichever comes first in the street can never be matched, because everything left in the other list is further away still, so drop it.

Pairing the nearest available officer with the nearest available thief is safe, which is the part worth arguing rather than assuming: any other thief that officer could reach lies further along and is therefore still reachable by a later officer, so committing to the nearest one never costs an arrest elsewhere. That is a standard exchange argument, the same shape as the ones on the greedy pairing page.

// cells: "P" police, "T" thief, "." empty. k = arrest range.
function catchThieves(cells, k) {
  const police = [], thieves = [];
  cells.forEach((c, i) => {
    if (c === "P") police.push(i);
    else if (c === "T") thieves.push(i);
  });

  let p = 0, t = 0, arrests = 0;
  while (p < police.length && t < thieves.length) {
    if (Math.abs(police[p] - thieves[t]) <= k) {
      arrests++; p++; t++;                   // nearest pair, always safe
    } else if (police[p] < thieves[t]) {
      p++;                                   // this officer reaches nobody
    } else {
      t++;                                   // this thief escapes everybody
    }
  }
  return arrests;
}

The celebrity problem

A room of n people. A celebrity is someone everybody knows and who knows nobody. You may ask one question: does A know B? Find the celebrity, or report that there is none.

There are no arrays here and nothing to sort, which is what makes this the best test of whether the technique has actually landed. Asking everybody about everybody is n² questions. Two pointers get it to about 3n, and the reason is that a single question always eliminates somebody:

• If A knows B, then A knows somebody, and a celebrity knows nobody. A is out.
• If A does not know B, then B is not known by everybody. B is out.

Either way one person leaves the running, so one pointer from each end and n-1 questions leave exactly one candidate standing.

// knows(a, b) is the one allowed question.
function findCelebrity(n, knows) {
  // Elimination: n - 1 questions leave one candidate.
  let lo = 0, hi = n - 1;
  while (lo < hi) {
    if (knows(lo, hi)) lo++;   // lo knows somebody, so lo is not it
    else hi--;                 // hi is not known by lo, so hi is not it
  }
  const candidate = lo;

  // Verification: the pass above proves who it cannot be, not who it is.
  for (let other = 0; other < n; other++) {
    if (other === candidate) continue;
    if (knows(candidate, other) || !knows(other, candidate)) return -1;
  }
  return candidate;
}

The same elimination is often written with a stack: push everybody, then repeatedly pop two and put the survivor back. It asks the same n-1 questions and needs the same verification. The two-pointer version is the same algorithm with the stack replaced by two indices, which is the recurring trade in this section - a pointer instead of a structure.

The section in one table

Check yourself

That is the section. If you want more of the same shape applied to sorted input, the merge-based problems and partition problems pages are the closest neighbours.