Two Sum

Find two numbers in an array that add up to a target value.

EasyTime O(n) · Space O(n)

Problem statement

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

Example

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9, so we return [0, 1]
You may assume each input has exactly one solution, and you may not use the same element twice.

Approach

A hash map gives an O(n) solution:

  1. 1
    Create an empty hash map to store numbers and their indices.
  2. 2
    Iterate through the array once.
  3. 3
    For each number, calculate its complement (target − current number).
  4. 4
    Check whether the complement is already in the hash map.
  5. 5
    If it is, return both indices. Otherwise add the current number to the map.

Why this works

Storing each number as we go lets us check in O(1) whether its complement has been seen, avoiding nested loops.

Solution

JavaScript
function twoSum(nums, target) {
  const map = new Map();
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return null;
}

Interactive visualizer

See the algorithm run step by step.

i=0
2
i=1
7
i=2
11
i=3
15
Hash Map
Empty
Step 1 / 0Infinity%

Time & space complexity

Time complexity

O(n)

Single pass through the array

Space complexity

O(n)

Hash map stores up to n elements

Discussion

Questions, ideas or a different approach? Join the conversation.