Two pointers and windows

The idea

A nested loop looks at every pair: n² of them. Two pointers look at each item a constant number of times, because each pointer only moves forwards and each can move at most n times. Two pointers, n moves each, 2n operations, O(n).

The requirement is that you can always tell which pointer to move without looking at anything else. That is usually true when the data is sorted, or when the property you are tracking is monotonic.

Converging pointers: two-sum on a sorted array

The nested-loop version is n². This one is n, and the reasoning is what matters: if the sum is too small, no pair using a[lo] can ever work, because a[hi] is already the largest available. So lo can move, permanently. Every step eliminates a whole row of the n² table.

function twoSum(a, target) {
  let lo = 0;
  let hi = a.length - 1;

  while (lo < hi) {
    const sum = a[lo] + a[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;          // need more: the only way is a bigger left
    else hi--;                       // need less: the only way is a smaller right
  }

  return null;
}

Same direction: removing duplicates in place

A read pointer and a write pointer, both moving forwards at different speeds. This is the shape of every in-place filter, compaction and partition — including the one in quicksort, which is the same pattern with a comparison instead of an equality test.

function dedupeSorted(a) {
  if (!a.length) return 0;
  let write = 0;                        // where the next kept item goes

  for (let read = 1; read < a.length; read++) {
    if (a[read] !== a[write]) a[++write] = a[read];
  }

  return write + 1;                     // the new length
}

The sliding window

A window is two pointers with a rule for when to grow and when to shrink. end always moves forwards; start only ever moves forwards too. Together they make one pass, even though the window itself expands and contracts.

The tell for "this is a window problem": a question about contiguous subarrays or substrings — longest, shortest, at most k of something, sum equal to something.

function longestUnique(text) {
  const lastSeen = new Map();
  let start = 0;
  let best = 0;

  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
      start = lastSeen.get(ch) + 1;      // the window jumps past the repeat
    }
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }

  return best;
}

The family

Five shapes, and between them they cover a large proportion of the "make this faster" problems you will ever be handed. The cost of the technique is that the data usually has to be sorted first — which is n log n, still far better than n².