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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Hash map | O(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