Two Sum Problem in Python
Find two numbers that add up to a target in a single pass, using a dictionary to remember what you have seen.
- The complement target - value
- Storing seen values in a dict
- O(n) time instead of O(n²)
index 0: 2need 7, not seen yet → seen = {2: 0}index 1: 7need 2, found at 0 → [0, 1]Look for the missing partner
The problem
Given a list of prices and a budget, which two items cost exactly the budget? Checking every pair works but takes about n² / 2 comparisons. Remembering what you have already seen makes it possible in one pass.
Think of it like this
Two Sum is like shopping with an exact budget. For each price tag you work out the amount still missing, then check your notes: have I already seen an item with exactly that price? If yes, the pair is found. If not, you note this price and where you saw it, and move on.
complement = target - value🤔 The price still missingif complement in seen:📋 Is that price already in my notes?return [seen[complement], index]🛍️ Found the pair: both positionsseen[value] = index✍️ Note this price and its position, then keep goingThe Two Sum problem asks for the positions of two numbers in a list that add up to a target; a dictionary of seen values solves it in one pass, O(n) time.
Key points
complement = target - valueis the value that would complete the pair.seenmaps each value already visited to its index, so lookups are fast.if complement in seen:finds the partner among earlier values.seen[value] = indexis stored after the check, so a value is never paired with itself.- For 9, the value 7 finds its partner 2 at index 0, giving
[0, 1].
When should you use it?
- Finding pairs with a given sum or difference.
- Learning to trade memory for speed with a hash table.
- A very common interview question and the base of 3-Sum and similar problems.
When not to use it
- Sorted input where memory is tight: two pointers from both ends use no extra memory.
- You need every pair, not just one: collect results instead of returning at the first match.
Example code
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Result of running the code
[0, 1]
Code explanation
The dictionary stores values already visited. Looking up the required complement makes the algorithm O(n) time with O(n) extra space.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Storing before checking
A value can pair with itself, such as 3 + 3 = 6 with only one 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
All challenges