Two sum (hash map)

Easy TimeO(n) SpaceO(n)

Given an array of integers nums in no particular order and a target, return the positions of the two values that add up to it. Exactly one pair does, no value may be paired with itself, and it is the positions that come back rather than the values.

Examples

Example 1

Input
nums = [7, 1, 4, 9, 3]target = 10
Output
[1,3]
1 + 9 = 10, and they sit at positions 1 and 3 with two other numbers between them.

Example 2

Input
nums = [7, 1, 4, 9, 3]target = 99
Output
[]
No two of the same five numbers add to 99, so nothing comes back.

The Code

function twoSum(nums, target) {
  const seen = {};
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen[need] !== undefined) return [seen[need], i];
    seen[nums[i]] = i;
  }
  return [];
}
twoSum([7, 1, 4, 9, 3], 10);
Done
Step through twoSum([7, 1, 4, 9, 3], 10) call by call

Explanation

Every value is remembered with its position, so a pair is found the moment its second half arrives rather than by trying every pair.

  1. 1

    need is target − nums[0], so 3. seen is empty, so there is nothing to pair with — and seen[7] = 0 records this number against its position.

    i
    7
    0
    1
    1
    4
    2
    9
    3
    3
    4

    need=3seen={}

    seen[7] = 0

  2. 2

    need is 10 − 1 = 9, which is not in seen either, so seen[1] = 1. This is the entry the answer comes out of.

    7
    0
    i
    1
    1
    4
    2
    9
    3
    3
    4

    need=9seen={7: 0}

    seen[1] = 1

  3. 3

    need is 10 − 4 = 6, a number this array never contains. seen[4] = 2.

    7
    0
    1
    1
    i
    4
    2
    9
    3
    3
    4

    need=6seen={7: 0, 1: 1}

    seen[4] = 2

  4. 4

    need is 10 − 9 = 1, and seen[1] is 1 — so the function returns those two positions, without ever reading the 3 at the end.

    7
    0
    1
    1
    4
    2
    i
    9
    3
    3
    4

    need=1seen={7: 0, 1: 1, 4: 2}

    return [1, 3]

More like this

All arrays & loops examples (10) →