How do you solve the Two Sum problem in JavaScript?
Quick answer
Walk through the array once while storing each number’s index in a hash map; for every number, check whether target minus that number is already in the map. This runs in O(n) time and O(n) space.
Problem
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Assume exactly one solution exists and you may not use the same element twice.
Input
Output
Constraints
- 2 ≤ nums.length ≤ 10⁴
- -10⁹ ≤ nums[i], target ≤ 10⁹
- Exactly one valid answer exists
Example
nums[0] + nums[1] = 2 + 7 = 9, so the answer is [0, 1].
Solution
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return []; // unreachable when a solution is guaranteed
}
twoSum([2, 7, 11, 15], 9); // [0, 1]Create an empty map from value to index.
For each element, compute the complement target - nums[i].
If the complement is already in the map, return its index and the current index.
Otherwise store the current value and index and continue.
Time complexity
Space complexity
Alternative approach
If the array is sorted (or you sort a copy that keeps the original indices), use two pointers from both ends and move them inward depending on whether the sum is too small or too large. That uses O(1) extra space but sorting costs O(n log n).
Discussion
The brute-force solution checks every pair with two nested loops. It is correct but takes O(n²) time, which is too slow for large inputs.
The key observation is that for each number x you are looking for one specific partner: target - x. A Map lets you check whether that partner has already been seen in constant time, so a single pass is enough.
Check for the complement before inserting the current number, otherwise an element could be paired with itself (for example target 6 and value 3 at one index).
Common mistakes
- Inserting the current number before checking, so it can pair with itself.
- Returning the values instead of the indices.
- Forgetting to mention the space cost of the hash map.
Follow-up questions
- How would you return all pairs instead of one?
- How do you solve Three Sum?