The problem
Given a list of numbers and a target, find the positions of two numbers that add up to the target. Exactly one such pair exists.
Input: nums = [3, 8, 5, 9, 4], target = 17 Output: [1, 3] (8 + 9 = 17)
Picture it
Think of a coat-check counter. Each arriving guest carries a number. Before hanging their coat, the attendant asks: “is there already a coat here whose number is exactly what this guest needs to reach the target?” If yes, those two guests are the pair. If not, the coat goes on the rack. The rack is a dictionary that maps number → position, so the check takes one glance instead of searching every coat.
How to recognise it
- You need two items that combine (add up, differ by) to a given value.
- The question asks for positions or existence, so you can stop at the first match.
- The input is not sorted and you must return original positions, so sorting would lose the indices.
- n up to 10^4 or more rules out checking every pair; one pass is expected.
- Once you fix x, the partner is fully determined (target − x). "The partner is known exactly" is the strongest hint for a dictionary lookup.
Start with brute force
Try every pair of positions (i, j) with i < j and check whether the two numbers add up to the target. It is correct and easy to write.
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
There are n(n − 1)/2 pairs, so time is O(n²) and extra space is O(1). With n = 10^4 that is about 5 × 10^7 pair checks; with n = 10^5 it is about 5 × 10^9, far too slow for a typical time limit.
From brute force to the idea
- Find the waste. For each i, the inner loop scans the rest of the list for one specific value, target − nums[i], searching from scratch every time.
- Turn the search into a lookup. A dictionary (Python's hash map) answers "is this value here?" in O(1) on average. So remember the numbers you have already passed.
- Look backwards, not forwards. Walk the list once. For x at position i, compute need = target − x. If need is in the dictionary, its stored position and i are the pair. Every pair is found when its second member arrives.
- Store after checking. Only then store x → i. Checking first stops a lone 3 pairing with itself when the target is 6.
This is the key idea: the partner is target − x, and a dictionary of what you have seen finds it in O(1).
The key idea
For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).
Python solution
def two_sum(nums, target):
seen = {} # coat rack: number -> ticket
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every pair is checked once | O(1): only two loop indices |
| Dictionary (shown code) | O(n): one pass, each lookup and insert is O(1) on average | O(n): in the worst case every number is stored before the pair appears |
Edge cases
- Empty list or one number: returns
[]. The problem promises a pair, so this only matters if you reuse the function. - Duplicates that form the answer (
[3, 3], target 6): returns[0, 1]; the first 3 is stored before the second is checked. - Using one number twice (
[3, 4], target 6): correctly returns[]. - Negatives and zero (
[-3, 4, 3, 90], target 0): returns[0, 2]. - Very large values: Python integers do not overflow. In Java or C++,
target - xcan overflow near the integer limits. - Several valid pairs (
[1, 2, 3, 4], target 5): returns[1, 2], the pair whose second member comes first, not[0, 3].
Common mistakes
- Inserting x before checking for its partner, which lets a single 3 "pair" with itself for target 6.
- Sorting first to use two pointers, then returning positions from the sorted list instead of the original one.
- Storing position → number instead of number → position, so the lookup is by the wrong key.
- Searching the dictionary's values (
need in seen.values()), which is O(n) per lookup and brings back O(n²).
Given a list of numbers and a target, return how many pairs of positions i < j have nums[i] + nums[j] == target. Numbers can repeat, so [2, 2, 2] with target 4 has 3 pairs. Describe your approach, then write it if you like.
Compare with our answer
Keep the same one pass, but the dictionary now stores how many times each number has been seen so far. When x arrives, every earlier copy of target − x forms a new pair with it, so add that count, then record x.
from collections import defaultdict
def count_pairs(nums, target):
seen = defaultdict(int) # number -> how many times seen so far
pairs = 0
for x in nums:
pairs += seen[target - x]
seen[x] += 1
return pairs
count_pairs([2, 2, 2], 4) is 3 and count_pairs([1, 5, 3, 3, 3], 6) is 4. Time O(n), space O(n).
A strong answer mentions: storing counts instead of positions, adding the count before incrementing (so a number never pairs with itself), and why this is still O(n).
1. You must find two positions in an unsorted list whose numbers differ by exactly k. Which approach fits best?
For each x the partner is fully determined (x − k or x + k), so a dictionary lookup works in O(1). Sorting loses the original positions, and binary search needs a sorted list.
2. Why is the shown solution O(n) time rather than O(n²)?
There is one loop over n numbers, and a hash lookup and insert cost O(1) on average. Python dictionaries keep insertion order, not sorted order, and use hashing, not binary search.
3. A learner moves seen[x] = i above the if need in seen: line. Which input now gives a wrong answer?
With the insert first, the 3 at position 0 finds itself (need 3 is already stored) and the function returns [0, 0]. In the other inputs no number is exactly half the target, so the order of the two lines does not change the result.
Score 60% or more and the lesson is marked complete.