Q1: Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Use a Hash Map to reduce lookup complexity to O(1).
Hash Map Two Sum Solution
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 [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]💡 As we iterate through nums, we calculate the complement required to reach target. If the complement exists in our map, we immediately return its stored index and the current index.
Key Takeaways
- Hash Map provides O(n) time complexity by storing complement values during iteration.
- Avoids the naive O(n²) nested loop approach.
Knowledge Check
What is the time and space complexity of the Hash Map solution for Two Sum?