Two Sum
Given an array of integers nums and an integer target, return the indices of two distinct elements that add up to target. Return an empty array if there is no solution. Return the smaller index first. You may assume at most one valid answer.
Examples
nums = [2, 7, 11, 15], target = 9 → [0, 1]
nums = [3, 2, 4], target = 6 → [1, 2]
Compare approaches
Brute force
Compare every distinct pair. Simple and correct, but repeated comparisons become expensive.
Time: O(n²) · Space: O(1)
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}Hash map
Store previously visited values and their indices. Each lookup is expected constant time.
Time: O(n) expected · Space: O(n)
function twoSum(nums, target) {
const seen = new Map();
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 [];
}Common traps
- Do not use the same index twice.
- Check the complement before inserting the current value.
- Return indices, not the values themselves.