Read Pointer, Write Pointer

The pointers do not have to start apart. Put both at the front and let one run ahead, and the same technique solves a different family of problems: rewriting an array in place, finding the shortest window that satisfies a condition, and reversing text without allocating a second copy.

The bookkeeping changes in one important way. In the converging shape, exactly one pointer moves per iteration and the loop ends when they meet. Here the fast pointer drives the loop and the slow one moves only when something is true, sometimes several times in a row. The code looks nested. It is not: both pointers only ever move forward, so between them they take at most 2n steps for the whole run.

Unique elements, in place

Given a sorted array, remove the duplicates without allocating a second array, and return how many distinct values are left. Sorted is what makes it easy: duplicates are adjacent, so a value only ever has to be compared against the last one kept.

Two pointers, and it is worth naming them for what they do rather than where they are. read visits every position and never stops. write marks the end of the answer being built at the front of the array. Everything before write is the result; everything from write onward is scratch the caller is told to ignore.

The comparison is against a[write - 1], the last value kept, and not against a[read - 1], the previous value read. On this input the two happen to agree, which is exactly why the bug survives testing: they come apart the moment a run of three or more duplicates appears, and comparing against the previous read starts letting the second copy of a triple through.

// Sorted input. Returns the count of unique values; a[0..count) holds them.
function removeDuplicates(a) {
  if (a.length === 0) return 0;

  let write = 1;
  for (let read = 1; read < a.length; read++) {
    // Against the last value KEPT, not the last value read.
    if (a[read] !== a[write - 1]) {
      a[write] = a[read];
      write++;
    }
  }
  return write;
}

Smallest subarray with a sum of at least the target

Now a window rather than a write cursor. Given an array of positive values and a target, find the shortest contiguous run whose sum reaches the target.

Both pointers mark the ends of a window. Extend it on the right until the sum reaches the target; once it does, record the length, then pull the left edge in for as long as the sum still qualifies. When it drops below, go back to extending on the right.

The complexity is the part worth being able to defend in an interview. There is a while inside a for, which looks like O(n²), but start never decreases and never passes end, so across the whole run it advances at most n times in total. Every element enters the window exactly once and leaves at most once, giving O(n).

// Positive values only. Returns 0 when no window reaches the target.
function smallestSubarray(a, target) {
  let best = Infinity;
  let start = 0, sum = 0;

  for (let end = 0; end < a.length; end++) {
    sum += a[end];

    // Shrink while the window still qualifies: a shorter one may too.
    while (sum >= target) {
      best = Math.min(best, end - start + 1);
      sum -= a[start];
      start++;
    }
  }
  return best === Infinity ? 0 : best;
}

Reverse the words of a sentence

Turn "the sky is blue" into "blue is sky the", in place. The one-line solution - split, reverse, join - allocates a list of words and a new string. The in-place solution is two passes of the converging swap loop from the previous page, which is what earns this problem its place here.

Reverse the entire string first. That puts the words in the right order and spells every one of them backwards. Then walk the result, find each word by its boundaries, and reverse it back.

Both phases are the identical loop: a pointer at each end of a range, swap, step inward, stop when they meet. Phase one runs it once over the whole string; phase two runs it once per word. Total work is O(n), because each character is swapped at most twice.

function reverseRange(chars, lo, hi) {
  while (lo < hi) {
    [chars[lo], chars[hi]] = [chars[hi], chars[lo]];
    lo++; hi--;
  }
}

function reverseWords(s) {
  const chars = [...s];

  // Phase 1: right word order, every word spelled backwards.
  reverseRange(chars, 0, chars.length - 1);

  // Phase 2: put each word the right way round again.
  let i = 0;
  while (i < chars.length) {
    if (chars[i] === " ") { i++; continue; }
    let j = i;
    while (j + 1 < chars.length && chars[j + 1] !== " ") j++;
    reverseRange(chars, i, j);
    i = j + 1;
  }
  return chars.join("");
}

Telling the two shapes apart

Check yourself

Next: triplets and quadruplets, where a fixed prefix plus a converging pair takes 3 Sum from O(n³) to O(n²).