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:
- 1Create an empty hash map to store numbers and their indices.
- 2Iterate through the array once.
- 3For each number, calculate its complement (target − current number).
- 4Check whether the complement is already in the hash map.
- 5If 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.