ENDEAR
Start free
algorithmfree

Two pointers

Find a pair in a sorted array that adds up to a target, in a single pass.

time
O(n)
space
O(1)

// step through it

step 1 / 11
1function twoSum(nums, target) {2  let lo = 0, hi = nums.length - 1;3  while (lo < hi) {4    const sum = nums[lo] + nums[hi];5    if (sum === target) return [lo, hi];6    if (sum < target) lo++;7    else hi--;8  }9  return null;10}
target
= 10
  1. 1lo
  2. 3
  3. 4
  4. 6
  5. 8
  6. 11hi

The array is sorted. lo starts at the left end, hi at the right end.

How it works

Put one pointer at each end of a sorted array. If the sum is too small, move the left pointer right; if it is too big, move the right pointer left. Every move rules out a whole set of pairs, so the search takes linear time instead of checking every pair.