Solve the Two Sum problem. Given a list of integers and a target, return the indices of the two numbers that add up to the target. What is the optimal complexity?
The hashmap approach solves Two Sum in O(n) time and O(n) space by storing each number's index as you iterate and checking whether the complement has already been seen. A brute-force nested loop is O(n²) and unnecessary.
How to think about it
How to approach this out loud
Start by saying what you’re doing and why, not just writing code. Something like: “I want to avoid the nested loop. For each number, I need to know if its complement has already appeared — so I’ll use a dict to store what I’ve seen so far. One pass, O(n).”
That framing tells the interviewer you know why the hashmap matters, not just that it’s the answer.
Building toward the solution
The complement insight: if nums[i] = 7 and target = 9, then you need index of 2. Instead of scanning the whole array again, you ask: “have I seen 2 before?” A dict makes that O(1).
You update the dict after checking — this naturally handles the case where you’d otherwise match a number with itself (e.g., target = 8, nums = [4, …]).
The solution
Why this works — single pass is enough
The single pass works because the problem is symmetric: if nums[j] is the complement of nums[i] (with j > i), then when we reach index j, nums[i] is already in seen. We never need to look forward, only backward.
Variant — return values instead of indices:
def two_sum_values(nums, target):
seen = set()
for x in nums:
if target - x in seen:
return (target - x, x)
seen.add(x)The hashmap pattern is the foundation for three-sum (fix one element, two-sum the rest) and many sliding-window problems. Whenever you hear “check if a value satisfying some relation exists,” reach for a dict or set.