The Two Pointer Technique

Two pointers is how you get hash-map speed without hash-map memory. It only works when the input has an order you can exploit - which is why the first move is so often to sort.

Why it works

A nested loop tries every pair: O(n squared). Two pointers works because each comparison lets you rule out a whole group of pairs at once, so each pointer only ever moves forward. Total movement is n, so the whole thing is O(n).

Variant 1: opposite ends

Start wide, move inward. Needs sorted input.

function twoSumSorted(sorted, target) {
  let left = 0
  let right = sorted.length - 1

  while (left < right) {
    const sum = sorted[left] + sorted[right]

    if (sum === target) return [left, right]

    // Too small? The only way up is a bigger left value.
    if (sum < target) left++
    // Too big? The only way down is a smaller right value.
    else right--
  }

  return []
}

// Indices 2 and 3 hold 4 and 6.
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10))  // [2, 3]

Read the two comments carefully - they are the whole justification. Because the array is sorted, moving a pointer discards every pair it was part of, and none of those could have been the answer.

Variant 2: same direction

Both pointers move forward at different speeds. One reads, one writes, or one leads and one trails.

function dedupeSorted(sorted) {
  if (sorted.length === 0) return sorted

  let write = 1

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

  sorted.length = write
  return sorted
}

console.log(dedupeSorted([1, 1, 2, 2, 2, 3]))  // [1, 2, 3]

When it does not apply

Two pointers needs the input to be ordered in a way that makes moving a pointer meaningful. On an unsorted array where you need exact matches, a Set is the right tool - sorting first would cost O(n log n) to save O(n) memory, which is rarely worth it.

The exception: if the input arrives sorted, or you need sorted output anyway, two pointers is free.

Recognising it

• The problem says sorted, or sorting does not break it.
• You are looking for a pair or a triple.
• The problem demands constant extra space.
• You are rearranging in place.