Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Two Sum

Find the two numbers in an array that add up to a target. From the O(n²) brute force to the O(n) hash map solution, in JavaScript and Python.

Updated Quick read: 3 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(1)
Hash mapO(n)O(n)

The problem

You are given an array of integers and a target number. Return the indexes of the two numbers that add up to the target. Exactly one pair works, and the same element cannot be used twice.

numbers = [2, 7, 11, 15], target = 9   →  [0, 1]    (2 + 7 = 9)
numbers = [3, 2, 4],      target = 6   →  [1, 2]    (2 + 4 = 6)

In the second example the answer is not [0, 0]: 3 + 3 is 6, but that would use the element at index 0 twice.

Approach 1: brute force

Try every pair.

JavaScript

function twoSumBruteForce(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) return [i, j];
    }
  }
  return [];
}

Python

def two_sum_brute_force(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

Starting j at i + 1 avoids pairing an element with itself and avoids checking each pair twice.

Time O(n²), because of the loop inside a loop. Space O(1).

Approach 2: hash map

Look at what the inner loop does. For a given numbers[i], it searches for one specific value: target - numbers[i], called the complement. Searching for a specific value is what a hash map does in constant time.

So walk through the array once. For each number, check whether its complement has already been seen. If it has, the pair is found. If not, record the number and its index and move on.

JavaScript

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

Python

def two_sum(numbers, target):
    index_by_value = {}
 
    for i, value in enumerate(numbers):
        complement = target - value
        if complement in index_by_value:
            return [index_by_value[complement], i]
        index_by_value[value] = i
    return []

Walkthrough

numbers = [2, 7, 11, 15], target = 9:

i numbers[i] complement In the map? Map afterwards
0 2 7 No 2 → 0
1 7 2 Yes, at index 0 return [0, 1]

Time O(n): one pass with a constant-time lookup per element. Space O(n): the map can hold every element.

Why the lookup comes before the insert

If the number were stored first, an element could match itself. With numbers = [3, 2, 4] and target = 6, storing 3 and then looking up 6 - 3 would find the same 3 and return [0, 0]. Checking first means the map only ever contains earlier elements.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

Python

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))  # [1, 2]

The comment after each line is the result you should see.

Common mistakes

  • Returning the values instead of the indexes. The map must store the index as its value.
  • Sorting the array first. Sorting changes the positions, so the original indexes are lost. If the input is already sorted, see Two Sum on a sorted array.

Original problem: LeetCode 1: Two Sum