Two sum (sorted, two pointers)

Easy TimeO(n) SpaceO(1)

Given a sorted array of integers nums and a target, determine whether a pair of numbers in it sums to that target, and report their positions rather than the numbers themselves.

Examples

Example 1

Input
nums = [1, 3, 4, 5, 7, 11]target = 9
Output
[2,3]
4 + 5 = 9, and the 4 and the 5 sit at positions 2 and 3.

Example 2

Input
nums = [1, 3, 4, 5, 7, 11]target = 100
Output
[-1,-1]
Even 11 + 7, the largest pair, is only 18 — no pair reaches 100.

The Code

function twoSum(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;
    else hi--;
  }
  return [-1, -1];
}
twoSum([1, 3, 4, 5, 7, 11], 9);
Done
Step through twoSum([1, 3, 4, 5, 7, 11], 9) call by call

Explanation

Every step throws away a set of pairs rather than testing one: too big means the larger number cannot be in any answer, too small means the smaller one cannot be, and the search closes in from both ends.

  1. 1

    Because the array is sorted, the pairs can be searched without looking at all of them. Start with the two ends — lo on the smallest number, hi on the largest — which is the largest sum any pair can have.

    lo
    1
    0
    3
    1
    4
    2
    5
    3
    7
    4
    hi
    11
    5

    1 + 11 = 12 > 9

  2. 2

    If 11 is already too big beside the smallest number in the array, it is too big beside every other one as well, so every pair using 11 can be dropped at once. hi steps back to 7.

    lo
    1
    0
    3
    1
    4
    2
    5
    3
    hi
    7
    4
    11
    5

    1 + 7 = 8 < 9

  3. 3

    The same argument the other way round: if 1 cannot reach 9 even beside the largest number left, no pair using 1 ever will, so every pair using 1 goes too. lo steps forward to 3.

    1
    0
    lo
    3
    1
    4
    2
    5
    3
    hi
    7
    4
    11
    5

    3 + 7 = 10 > 9

  4. 4

    Over the target, so the larger number goes: hi steps back to 5.

    1
    0
    lo
    3
    1
    4
    2
    hi
    5
    3
    7
    4
    11
    5

    3 + 5 = 8 < 9

  5. 5

    Under the target, so the smaller number goes: lo steps forward to 4 — and the pair lands on the target. The answer is the positions those two sit at, 2 and 3. Had the pointers met without ever matching, there would have been no pair to find.

    1
    0
    3
    1
    lo
    4
    2
    hi
    5
    3
    7
    4
    11
    5

    4 + 5 = 9

More like this

All two pointers examples (9) →