Overview
Find two indices whose values add up to a target using a hash map for O(n) performance.
Analogy
At a party, remember everyone's name (hash map); when you meet someone, check if you've already seen their complement.
Step-by-step
- Create seen = {}.
- For each (i, num) in enumerate(nums):
- complement = target - num.
- If complement in seen: return [seen[complement], i].
- Else: seen[num] = i.
Visual
[2,7,11,15], target=9 → see 2(comp=7,no) → see 7(comp=2,yes) → [0,1]
Common mistakes
- Returning indices incorrectly (return the stored index, not the complement).
- Using nested loop O(n²) when O(n) with hash map is expected.
Practice questions
- Extend to three-sum: sort + two-pointer.
- Handle duplicates: return all pairs, not just the first.
AI Wisdom