07. 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.
How It Works & Algorithmic Design
This is solved using the Hash Map Complement Pattern:
- Mathematical Relation: For any element $x = \text{nums}[i]$, its required complementary pair is $y = \text{target} - x$.
- Hash Map Storage: Maintain a Hash Map where key =
array element valueand value =array index. - Single Pass: Loop through
numsusing index $i$:- Compute
complement = target - nums[i]. - Check if
complementexists in the Hash Map. - If it exists, return
[hashMap.get(complement), i]. - If not, insert
hashMap.put(nums[i], i)and continue.
- Compute
Why This Approach Works Best
Brute force nested loops take $O(n^2)$ time. Sorting followed by two pointers takes $O(n \log n)$ time and loses original indices. Hash Map lookup gives optimal $O(n)$ runtime and $O(n)$ space complexity.
Example Walkthrough
Input:
nums = [2, 7, 11, 15], target = 9Target sum is 9.
Step 0 (i=0, num=2):
Complement = 9 - 2 = 7. Map is empty -> Store {2: 0}No complement yet.
Step 1 (i=1, num=7):
Complement = 9 - 7 = 2. Found 2 in map at index 0!Match found.
Output:
[0, 1]Indices of values 2 and 7.
Answer: Two Sum using complement Hash Map
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 [];
}💡 Look up the target complement in a Hash Map during a single pass traversal.
Key Takeaways
- Store visited elements in a map to turn $O(n^2)$ pair searches into $O(1)$ lookups.
- Calculating
complement = target - currentavoids nested loops. - Optimal single-pass runtime of $O(n)$ time and $O(n)$ space.