Two pointers

Walk sorted data from two positions at once, moving whichever pointer can only improve the answer.

Start with the first problem

Draft. This pattern and its problems have not been reviewed by a second person yet.

When data is sorted, its order tells you which way to move. Two pointers keep a position each, in one list or two, and at every step one of them moves forward. Neither ever moves back, so the whole walk is linear.

Merging two sorted lists is the plainest case: compare the two front items, take the smaller, and move that pointer. Every item is taken exactly once.

From both ends of one sorted list, the pointers answer pair questions. If the pair at the two ends adds up to too little, the left item is too small to pair with anything; move it right. Too much, and the right item is too large for anything; move it left. Each move rules out a whole row of pairs at once, which is why it beats checking them all.

The bugs are at the edges: stopping when one list runs out and forgetting what is left in the other, or letting the two ends meet and pairing an item with itself.

Recognise it

  • The input is sorted, or sorting it first is allowed.
  • You need a pair, or to combine two ordered sequences.
  • Moving one end can only make the current candidate bigger, or only smaller.

The shape of the code

let i = 0, j = items.length - 1;
while (i < j) {
  const value = combine(items[i], items[j]);
  // record the best answer so far
  if (tooSmall(value)) i++;
  else j--;
}

Problems

In order of difficulty
  1. Not started
  2. Not started
Esc
↑ ↓ to move↵ to open