Practice: Two Sum
The classic interview question.
Given a list of numbers and a target, find the positions of two numbers that add up to the target. The list isn't sorted, so two pointers won't work directly. Pause and think. How could a dictionary help?

- Two numbers that add to a target
- The list isn't sorted
- How could a dict help?
The slow way
The obvious answer tries every pair, with a loop inside a loop. It works, but it's O of N squared. With a hundred thousand numbers, that's billions of checks.
def two_sum_slow(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
print(two_sum_slow([2, 7, 11, 15], 9))(0, 1)
The fast way
For each number, we ask, what partner do I need? That's the target minus the number. A dictionary remembers every number we've seen, and where it was. If the partner is already in the dictionary, we're done. Otherwise, we store this number, and move on. Run it. One pass, so it's O of N.
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
need = target - n
if need in seen:
return seen[need], i
seen[n] = i
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 8, 4, 5], 9))(0, 1) (2, 3)
Summary
Two sum asks, what partner do I need, and a dictionary remembers what we've seen. That turns O of N squared into O of N. It's a pattern you'll use again and again.
Key takeaways- need = target - n
- Remember what you've seen
- O(n) with a dict