ENDEAR
Start free
algorithmfree

Two sum with a hash map

Find two numbers that add up to a target in one pass, even in an unsorted array.

time
O(n)
space
O(n)

// step through it

step 1 / 9
1function twoSum(nums, target) {2  const seen = new Map();3  for (let i = 0; i < nums.length; i++) {4    const need = target - nums[i];5    if (seen.has(need)) return [seen.get(need), i];6    seen.set(nums[i], i);7  }8  return null;9}
target
= 9
  1. 3
  2. 8
  3. 2
  4. 7
  5. 5
seenempty

Start with an empty map seen. It will remember each number and its index.

How it works

For each number, work out the partner it needs to reach the target, then ask a hash map whether that partner has already appeared. Lookups take O(1) on average, so one pass is enough: O(n) time. The price is memory: the map can hold up to n numbers, so O(n) space. Trading space for time like this is one of the most common moves in coding problems.

Practice spotting this pattern →