Two Sum - find two numbers that add up to a target
Walk through the array once and store each number's index in a hash map. For each number, check if target minus that number is already in the map. This takes O(n) time.
Explain it simply
You are given a list of numbers and a target, and you must return the positions of two numbers that add up to the target. Imagine you are at a shop with a gift voucher of ₹9. As you look at each item's price, you ask: "Have I already seen an item that costs exactly ₹9 minus this price?" Keeping a notebook of prices you have seen (a hash map) lets you answer that instantly instead of walking back through the whole shop every time.
Line by line
function twoSum(nums, target) {
const seen = new Map(); // value -> index where we saw it
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]; // the partner we are looking for
if (seen.has(need)) {
return [seen.get(need), i]; // found both positions
}
seen.set(nums[i], i); // remember this value for later numbers
}
return []; // no pair found
}
console.log(twoSum([2, 7, 11, 15], 9)); // Output: [0,1]
console.log(twoSum([3, 2, 4], 6)); // Output: [1,2]
console.log(twoSum([3, 3], 6)); // Output: [0,1]needis the number that would complete the pair.- We check the map before adding the current number, so a number is never paired with itself.
- The map stores the first index of each value, which is enough to answer the question.
Approaches
- Brute force: try every pair with two loops. Simple, but it checks about n²/2 pairs.
- Sort and two pointers: sort a copy with original indexes, then move pointers inward from both ends. Good when you cannot use extra memory for a map, but sorting costs O(n log n).
- Hash map (best for this problem): one pass, as shown above.
Complexity
| Approach | Time | Extra space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Sort + two pointers | O(n log n) | O(n) for the index pairs |
| Hash map | O(n) | O(n) |
Common mistakes
- Returning the values instead of the indexes.
- Adding the current number to the map before checking, which can pair a number with itself (for example target 6 and a single 3).
- Forgetting that the same value can appear twice, like
[3, 3].
What to say in the interview
"I would first mention the brute force O(n²) solution, then improve it. While scanning the array once, I keep a hash map from value to index. For each number I compute the complement, target minus the number. If the complement is already in the map, I return both indexes; otherwise I store the current number. That is O(n) time and O(n) space. I check the map before inserting so a number is not used twice."
Follow-up questions
- How would you return all pairs instead of one?
- What changes if the array is already sorted?
- How would you solve Three Sum?