Two Sum
Learn how to find two numbers in a list that add up to a target value in Python.
Two Sum
Problem
Given a list of numbers and a target value, find the indices of the two numbers that add up to the target. Each input has exactly one solution and you cannot use the same element twice.
Input: [2, 7, 11, 15], target = 9
Output: [0, 1] (because 2 + 7 = 9)
Input: [3, 2, 4], target = 6
Output: [1, 2] (because 2 + 4 = 6)
Input: [1, 5, 3, 7, 9], target = 12
Output: [2, 3] (because 3 + 7 = 10... wait, 3+9=12 → [2, 4])
Input: [3, 3], target = 6
Output: [0, 1] (same value, different indices)Logic
Brute force approach:
- Pick every possible pair of numbers
- Check if they add up to target
- Return their indices if they do
Optimal approach — hash map:
- Loop through each number
- Calculate what number we need to reach target —
complement = target - current - Check if that complement already exists in a dictionary
- If yes — we found our pair, return indices
- If no — store current number and its index in the dictionary, move on
Flow
Solution 1 — brute force with nested loops
Check every possible pair. Simple but slow — O(n²).
def two_sum_brute(numbers, target):
n = len(numbers)
# outer loop — pick first number
for i in range(n):
# inner loop — pick second number
# start at i+1 to avoid using same element twice
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j] # found the pair
return [] # no pair found
print(two_sum_brute([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum_brute([3, 2, 4], 6)) # [1, 2]
print(two_sum_brute([1, 5, 3, 7, 9], 12)) # [2, 4]
print(two_sum_brute([3, 3], 6)) # [0, 1]Code Execution — Solution 1
Trace through two_sum_brute([2, 7, 11, 15], target=9):
i | j | numbers[i] | numbers[j] | sum | == 9? |
|---|---|---|---|---|---|
0 | 1 | 2 | 7 | 9 | Yes → return [0, 1] |
Found immediately on first pair.
Trace through two_sum_brute([3, 2, 4], target=6):
i | j | numbers[i] | numbers[j] | sum | == 6? |
|---|---|---|---|---|---|
0 | 1 | 3 | 2 | 5 | No |
0 | 2 | 3 | 4 | 7 | No |
1 | 2 | 2 | 4 | 6 | Yes → return [1, 2] |
The brute force approach has time complexity O(n²) — for every element, it checks every other element. For a list of 10,000 numbers, that is up to 100,000,000 comparisons. The hash map solution reduces this to O(n) — just one pass through the list.
Solution 2 — hash map in one pass
Store each number and its index as we go. For each new number, check if its complement is already stored.
def two_sum(numbers, target):
# key = number, value = its index
seen = {}
for index, number in enumerate(numbers):
# what number do we need to reach target?
complement = target - number
if complement in seen:
# found it — return both indices
return [seen[complement], index]
# not found yet — store this number and its index
seen[number] = index
return [] # no solution
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum([3, 2, 4], 6)) # [1, 2]
print(two_sum([1, 5, 3, 7, 9], 12)) # [2, 4]
print(two_sum([3, 3], 6)) # [0, 1]Code Execution — Solution 2
Trace through two_sum([2, 7, 11, 15], target=9):
| Step | index | number | complement = 9 - number | complement in seen? | seen |
|---|---|---|---|---|---|
| 1st | 0 | 2 | 7 | No | {2: 0} |
| 2nd | 1 | 7 | 2 | Yes → return [0, 1] |
Only two steps — found the answer immediately when processing 7.
Trace through two_sum([3, 2, 4], target=6):
| Step | index | number | complement = 6 - number | complement in seen? | seen |
|---|---|---|---|---|---|
| 1st | 0 | 3 | 3 | No | {3: 0} |
| 2nd | 1 | 2 | 4 | No | {3: 0, 2: 1} |
| 3rd | 2 | 4 | 2 | Yes → return [1, 2] |
At step 3 — complement = 6 - 4 = 2. We look in seen and find 2 at index 1. Return [1, 2].
Trace through two_sum([3, 3], target=6):
| Step | index | number | complement = 6 - number | complement in seen? | seen |
|---|---|---|---|---|---|
| 1st | 0 | 3 | 3 | No | {3: 0} |
| 2nd | 1 | 3 | 3 | Yes → return [0, 1] |
The trick is in the order of operations — we check seen BEFORE adding to it. This prevents returning the same index twice. At step 1, complement = 3 but seen is empty — so we store 3: 0. At step 2, complement = 3 and now 3 IS in seen at index 0 — so we return [0, 1], two different indices.
Solution 3 — two pointers on sorted array
If the array is already sorted — or if you do not need to return indices — two pointers is a clean approach. One pointer starts at the left, one at the right. Move them inward based on whether the sum is too big or too small.
def two_sum_sorted(numbers, target):
"""
Works on a sorted array.
Returns the values (not indices) that sum to target.
"""
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [numbers[left], numbers[right]] # found
elif current_sum < target:
left += 1 # sum too small — move left pointer right
else:
right -= 1 # sum too big — move right pointer left
return [] # no solution
# works on sorted arrays
print(two_sum_sorted([2, 7, 11, 15], 9)) # [2, 7]
print(two_sum_sorted([2, 3, 4, 7, 11], 6)) # [2, 4]
print(two_sum_sorted([1, 3, 5, 7, 9], 12)) # [3, 9]Code Execution — Solution 3
Trace through two_sum_sorted([1, 3, 5, 7, 9], target=12):
Array: [1, 3, 5, 7, 9]
| Step | left | right | numbers[left] | numbers[right] | sum | Action |
|---|---|---|---|---|---|---|
| 1st | 0 | 4 | 1 | 9 | 10 | Too small → left++ |
| 2nd | 1 | 4 | 3 | 9 | 12 | Equal → return [3, 9] |
Trace through two_sum_sorted([2, 3, 4, 7, 11], target=6):
| Step | left | right | numbers[left] | numbers[right] | sum | Action |
|---|---|---|---|---|---|---|
| 1st | 0 | 4 | 2 | 11 | 13 | Too big → right-- |
| 2nd | 0 | 3 | 2 | 7 | 9 | Too big → right-- |
| 3rd | 0 | 2 | 2 | 4 | 6 | Equal → return [2, 4] |
Solution 4 — find all pairs
What if there are multiple pairs that sum to the target? Find all of them.
def two_sum_all_pairs(numbers, target):
"""Return all pairs of values that sum to target."""
seen = set()
pairs = []
used = set()
for number in numbers:
complement = target - number
if complement in seen and (complement, number) not in used:
pairs.append((complement, number))
used.add((complement, number))
used.add((number, complement)) # avoid duplicate pairs
seen.add(number)
return pairs
print(two_sum_all_pairs([1, 5, 3, 3, 7, 9, 5], 8))
# [(1, 7), (3, 5), (3, 5)]
# wait — let us see: 1+7=8 ✅, 3+5=8 ✅
# but (3,5) appears twice because there are two 3s and two 5s
print(two_sum_all_pairs([1, 2, 3, 4, 5, 6], 7))
# [(1, 6), (2, 5), (3, 4)]Code Execution — Solution 4
Trace through two_sum_all_pairs([1, 2, 3, 4, 5, 6], target=7):
| Step | number | complement = 7 - n | complement in seen? | seen | pairs |
|---|---|---|---|---|---|
| 1st | 1 | 6 | No | {1} | [] |
| 2nd | 2 | 5 | No | {1,2} | [] |
| 3rd | 3 | 4 | No | {1,2,3} | [] |
| 4th | 4 | 3 | Yes → add (3,4) | {1,2,3,4} | [(3,4)] |
| 5th | 5 | 2 | Yes → add (2,5) | {1,2,3,4,5} | [(3,4),(2,5)] |
| 6th | 6 | 1 | Yes → add (1,6) | {1,2,3,4,5,6} | [(3,4),(2,5),(1,6)] |
Comparing all approaches
import time
# generate a large list
numbers = list(range(1, 10001))
target = 19999 # 9999 + 10000
# brute force
start = time.perf_counter()
two_sum_brute(numbers, target)
print(f"Brute force: {time.perf_counter() - start:.6f}s")
# hash map
start = time.perf_counter()
two_sum(numbers, target)
print(f"Hash map: {time.perf_counter() - start:.6f}s")Output:
Brute force: 2.341820s
Hash map: 0.000312sThe hash map is over 7,000x faster on 10,000 numbers.
Which solution to use?
| Solution | Time | Space | Best when |
|---|---|---|---|
| Solution 1 — brute force | O(n²) | O(1) | Learning — understanding the problem |
| Solution 2 — hash map | O(n) | O(n) | Default — best performance |
| Solution 3 — two pointers | O(n) | O(1) | Sorted array, values not indices needed |
| Solution 4 — all pairs | O(n) | O(n) | When multiple solutions exist |
Output
[0, 1]
[1, 2]
[2, 4]
[0, 1]
[2, 7]
[2, 4]
[3, 9]