Skip to content
../writing

Two Pointers

Naseebullah AhmadiSenior Software Engineer, London

Checking every pair in an array costs n² comparisons. If the array is sorted, one comparison can rule out a whole row of pairs at once, and the nested loop collapses into a single pass.

#arrays
#strings
#patterns
#interviews
7 min read
#algorithms

Here's the question: in this sorted array, which two numbers add up to 10?

  1. Index 0: 1
  2. Index 1: 3
  3. Index 2: 4
  4. Index 3: 6
  5. Index 4: 8
  6. Index 5: 11
Six sorted numbers, target 10. Brute force checks all 15 pairs.

Brute force tries every pair: 15 of them here, n² / 2 in general. Two pointers finds the answer in 5 steps, and the reason is worth seeing rather than memorising.

One comparison rules out a whole row

Put one pointer on the smallest number and one on the largest, and add them.

  1. Index 0: 1 (L)
  2. Index 1: 3
  3. Index 2: 4
  4. Index 3: 6
  5. Index 4: 8
  6. Index 5: 11 (R: out)
1 + 11 = 12, too big. And 1 is the smallest partner 11 will ever get, so every pair with 11 is too big. Drop 11.

12 is over the target. That doesn't just rule out the pair (1, 11): 1 is the smallest number in the array, so 11 plus anything else is even bigger. Every pair containing 11 is now dead, and one comparison removed five pairs.

  1. Index 0: 1 (L: out)
  2. Index 1: 3
  3. Index 2: 4
  4. Index 3: 6
  5. Index 4: 8 (R)
  6. Index 5: 11
1 + 8 = 9, too small. 8 is now the largest partner 1 can get, so every pair with 1 is too small. Drop 1.

The mirror image: 9 is under the target, and 8 is the largest number still in play, so 1 can't reach 10 with anything. Drop 1.

That's the whole pattern. Too big, move the right pointer in; too small, move the left pointer in. Each step permanently deletes one number, so the walk ends in at most n steps.

StepLRSumDecision
111112too big, drop 11
2189too small, drop 1
33811too big, drop 8
4369too small, drop 3
54610found

The sort is what makes the "drop" safe. On unsorted input, 1 isn't guaranteed to be the smallest partner, the reasoning breaks, and the pointers silently skip valid answers.

Two indices, one loop

@itsnas pair-sum.ts
codepair-sum.ts
// Sorted array: does a pair sum to target?
function pairSum(
  nums: number[],
  target: number,
): [number, number] | null {
  let left = 0
  let right = nums.length - 1
 
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++ // need a bigger value
    else right-- // need a smaller value
  }
 
  return null
}
main
Nas (@itsnas)

O(n)O(n) time and O(1)O(1) space. If you have to sort the input first, the O(nlog⁡n)O(n \log n) sort dominates. The guard is left < right because a pair needs two distinct elements; use <= only when a single middle element is a valid answer.

Same move, other shapes

The pointers don't always start at opposite ends. What stays the same is that a single comparison tells you which side can never help.

ShapePointersClassic problems
Opposite endsclose in from both sidespair sums, palindromes, container
Read and writeboth from the left, one lagsin-place dedupe, move zeroes to the end
Fast and slowone moves twice as fastcycle detection, middle of a linked list
Sliding windowboth from the left, keep a totallongest substring, subarray sums

When a problem says "sorted", "in place", "O(1) extra space" or "find two that...", ask which side one comparison lets you throw away. If you can answer, it's two pointers.

Two Sum II - Input Array Is SortedMedium
Valid PalindromeEasy
Remove Duplicates from Sorted ArrayEasy
3SumMedium
Container With Most WaterMedium
Trapping Rain WaterHard