Two Sum is the most frequently asked coding problem there is, and that's exactly why it's useful: the interviewer already knows the answer, so they're grading how you get there. This lesson runs the full six-step loop on it, out loud, from the clarifying questions to the follow-ups. Every step builds on lessons 0.1 to 0.5: hidden costs, constraints, memory trade-offs and the right Python structures.
The problem. Given a list of integers nums and an integer target, return the indices of two different
elements whose values add up to target.
nums = [3, 8, 1, 6, 4], target = 10 → (3, 4) because 6 + 4 = 10
ML context. The core idea, "look up the complement in a hash map", is the hash join at the heart of data pipelines: matching training rows to labels by key, joining feature tables on user ID, finding pairs of items whose costs fit a budget exactly.
1. Step 1: Clarify
Say these questions out loud; each one changes the code or the algorithm.
| Question | Typical answer | Why you asked |
|---|---|---|
| Is there always exactly one solution? | Yes (classic version) | If not: return what? None? All pairs? |
| Can I use the same element twice? | No | [3], target 6 must not return (0, 0) |
| Can values repeat? | Yes | [3, 3], target 6 → (0, 1) is valid |
| Negative numbers? Zero? | Yes | Rules out tricks that assume positives |
| Return indices or values? In what order? | Indices, any order | Sorting loses original indices unless you keep them |
| How large is n? | Up to 10⁴ (classic), follow-up: 10⁵+ | Decides whether O(n²) is acceptable |
| Is the input sorted? | No | Sorted input unlocks a different solution |
Constraint arithmetic: at n = 10⁴, n²/2 = 5 × 10⁷ pair checks: a few seconds in Python, borderline. At n = 10⁵ it's 5 × 10⁹: far too slow. So expect to optimise, and say so.
2. Step 2: Brute force
Try every pair (i, j) with i < j.
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n): # j > i: different elements, each pair once
if nums[i] + nums[j] == target:
return (i, j)
return None
assert two_sum_brute([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_brute([3, 3], 6) == (0, 1)
assert two_sum_brute([3], 6) is None # can't reuse the single 3
assert two_sum_brute([-2, 7, 11, 5], 3) == (0, 3)
print("brute force works")
- Correctness: every pair is checked, so if a valid pair exists, it's found.
j > iprevents reusing an element. - Time: n(n − 1)/2 checks in the worst case: O(n²).
- Space: O(1).
- Verdict against the constraints: fine for n ≤ a few thousand; too slow at 10⁵. Optimise.
3. Step 3: Optimise, from first principles
What is the brute force really doing? For each nums[i], it searches the rest of the list for one specific value:
target − nums[i], the complement. Searching a list is O(n). So the question becomes: how do I find a specific
value faster than scanning? There are two classic answers: order (sorting) and hashing.
Optimisation 1: sort, then walk two pointers inward
If the values were sorted, we could start with the smallest and the largest:
- If their sum is too small, the smallest value can't be part of any solution with anything (the largest partner is already too small), so move the left pointer right.
- If the sum is too big, the largest value is too big for every partner, so move the right pointer left.
- If it equals the target, done.
Each step discards one value forever, so the walk takes at most n steps. Sorting loses the original positions, so we sort (value, original index) pairs.
def two_sum_sorted_pointers(nums, target):
pairs = sorted((v, i) for i, v in enumerate(nums)) # O(n log n); keeps original indices
left, right = 0, len(pairs) - 1
while left < right:
total = pairs[left][0] + pairs[right][0]
if total == target:
i, j = pairs[left][1], pairs[right][1]
return (min(i, j), max(i, j))
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return None
assert two_sum_sorted_pointers([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_sorted_pointers([3, 3], 6) == (0, 1)
assert two_sum_sorted_pointers([3], 6) is None
print("sort + two pointers works")
- Time: O(n log n) to sort + O(n) to walk = O(n log n).
- Space: O(n) for the (value, index) pairs.
- Why it's correct: a value is discarded only when it cannot be in any solution with the remaining values, so we never skip the answer.
Optimisation 2: one pass with a hash map
The two-pointer version still pays O(n log n) for sorting. Can we find the complement in O(1)? Yes: remember every
value we've seen, with its index, in a dict. For each new value x, check whether target − x is already there.
def two_sum_hash(nums, target):
seen = {} # value -> index where we saw it
for j, x in enumerate(nums):
need = target - x
if need in seen: # O(1) average
return (seen[need], j)
seen[x] = j # store AFTER checking: never pair x with itself
return None
assert two_sum_hash([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_hash([3, 3], 6) == (0, 1) # second 3 finds the first
assert two_sum_hash([3], 6) is None # single 3 can't pair with itself
assert two_sum_hash([0, 4, 3, 0], 0) == (0, 3)
print("one-pass hash map works")
- Time: one pass, O(1) average per step: O(n).
- Space: O(n) for the map.
- The subtle line: storing
xafter checking means an element can never pair with itself, which handles[3]with target 6, while[3, 3]still works because the second 3 finds the first.
Quick check
In the one-pass hash map, why is seen[x] = j placed after the need in seen check rather than before?
Show the answer
B. Storing first would let x find itself when target = 2x, wrongly pairing an element with itself — Checking before storing guarantees the complement came from an earlier, different index.
4. Step 4: Code cleanly
The hash version is the one to present by default. Its clean form is above; the habits:
seen,need,j: names that explain themselves.- Return as soon as the answer is known.
- Handle "no solution" explicitly (
return None) even if the problem promises one; say so.
5. Step 5: Test, against the brute force
Random tests can have several valid answers, so test the property (different indices, correct sum) and agreement on whether a solution exists, rather than exact index pairs.
import random
def two_sum_brute(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)
return None
def two_sum_sorted_pointers(nums, target):
pairs = sorted((v, i) for i, v in enumerate(nums))
left, right = 0, len(pairs) - 1
while left < right:
total = pairs[left][0] + pairs[right][0]
if total == target:
i, j = pairs[left][1], pairs[right][1]
return (min(i, j), max(i, j))
if total < target:
left += 1
else:
right -= 1
return None
def two_sum_hash(nums, target):
seen = {}
for j, x in enumerate(nums):
if target - x in seen:
return (seen[target - x], j)
seen[x] = j
return None
def valid(nums, target, answer):
if answer is None:
return True
i, j = answer
return i != j and nums[i] + nums[j] == target
edge_cases = [([], 5), ([5], 10), ([5, 5], 10), ([1, 2], 4), ([-3, 3], 0), ([0, 0, 0], 0), ([10**9, -10**9], 0)]
rng = random.Random(9)
random_cases = [([rng.randint(-15, 15) for _ in range(rng.randint(0, 12))], rng.randint(-20, 20)) for _ in range(1000)]
for nums, target in edge_cases + random_cases:
reference = two_sum_brute(nums, target)
for fn in (two_sum_sorted_pointers, two_sum_hash):
got = fn(nums, target)
assert valid(nums, target, got), (fn.__name__, nums, target, got)
assert (got is None) == (reference is None), (fn.__name__, nums, target)
print("all versions agree on", len(edge_cases) + len(random_cases), "cases")
6. Step 6: Complexity, and the comparison
| Approach | Time | Extra space | Use when |
|---|---|---|---|
| Brute force | O(n²) | O(1) | n small; simplest to trust |
| Sort + two pointers | O(n log n) | O(n) (indices) | input sorted, or memory matters |
| One-pass hash map | O(n) average | O(n) | the default answer |
7. When the constraints change: the follow-ups
Interviewers almost always follow up with a changed constraint. Each one has a crisp answer.
Follow-up A: the input is already sorted (return 1-based indices)
Sorting is free, so the two-pointer walk needs no extra memory at all: O(n) time, O(1) space. This beats the hash map on memory.
Trace it by hand before coding, the way you would at the whiteboard, on [1, 3, 4, 6, 8] with target 10: (1, 8) = 9
→ move left; (3, 8) = 11 → move right; (3, 6) = 9 → move left; (4, 6) = 10 ✓, 1-based positions 3 and 4. Writing the
trace first gives you the expected answer for your test, and catches off-by-one mistakes before they reach code.
def two_sum_sorted_input(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return (left + 1, right + 1)
if s < target:
left += 1
else:
right -= 1
return None
assert two_sum_sorted_input([1, 3, 4, 6, 8], 10) == (3, 4) # 4 + 6 = 10, from the trace
assert two_sum_sorted_input([2, 7, 11, 15], 9) == (1, 2)
assert two_sum_sorted_input([1, 2], 10) is None
print("sorted-input two pointers works")
Follow-up B: count all pairs (values can repeat)
"How many pairs (i < j) sum to the target?" Now we can't stop at the first match. For each value, the number of
earlier values equal to its complement is the number of new pairs it forms, so store counts, not indices.
from collections import Counter
def count_pairs(nums, target):
seen = Counter()
pairs = 0
for x in nums:
pairs += seen[target - x] # every earlier complement forms a pair with x
seen[x] += 1
return pairs
def count_pairs_brute(nums, target):
n = len(nums)
return sum(nums[i] + nums[j] == target for i in range(n) for j in range(i + 1, n))
import random
rng = random.Random(4)
for _ in range(500):
nums = [rng.randint(-5, 5) for _ in range(rng.randint(0, 15))]
t = rng.randint(-6, 6)
assert count_pairs(nums, t) == count_pairs_brute(nums, t)
assert count_pairs([1, 1, 1, 1], 2) == 6 # C(4, 2)
print("pair counting works: O(n) time, O(n) space")
Follow-up C: memory is very tight and you only need the values
Sort in place (nums.sort()) and walk two pointers: O(n log n) time, O(1) extra (beyond the sort's
internals). We trade time for memory.
Follow-up D: many targets, same array
Build a value → count map once (O(n)); each query checks complements with a pass over the distinct values. If the same targets repeat, cache their answers. Precompute once, reuse many times (lessons 0.2 and 0.3).
Follow-up E: a stream of add(number) and find(target) calls
Design a class. Which operation should be cheap depends on the workload, a constraint in its own right:
from collections import Counter
class TwoSumStore:
"""add is O(1); find is O(distinct values). Good when adds outnumber finds."""
def __init__(self):
self.counts = Counter()
def add(self, number):
self.counts[number] += 1
def find(self, target):
for x, c in self.counts.items():
y = target - x
if y != x and y in self.counts:
return True
if y == x and c >= 2: # the same value twice needs two copies
return True
return False
store = TwoSumStore()
for v in (1, 3, 5):
store.add(v)
assert store.find(4) is True # 1 + 3
assert store.find(7) is False
assert store.find(2) is False # only one 1
store.add(1)
assert store.find(2) is True # now 1 + 1
print("stream design works")
If find were far more frequent than add, you'd flip the trade: keep a set of all pairwise sums on every add
(O(n) per add) so each find is O(1). The workload is a constraint.
| Follow-up constraint | Best answer | Time | Space |
|---|---|---|---|
| Classic, unsorted | One-pass hash map | O(n) | O(n) |
| Already sorted | Two pointers | O(n) | O(1) |
| Count pairs, duplicates | Counter of complements | O(n) | O(n) |
| Memory tight, values only | Sort in place + two pointers | O(n log n) | O(1) |
| Stream, many adds | Counter; scan on find | add O(1), find O(n) | O(n) |
| Stream, many finds | Store all pair sums | add O(n), find O(1) | O(n²) |
| Three numbers (3Sum) | Sort + fix one + two pointers | O(n²) | O(1) |
Quick check
The interviewer asks for all triples summing to zero (3Sum). How does Two Sum's thinking extend?
Show the answer
A. Sort once, fix each element as the first, then run the sorted two-pointer Two Sum on the rest for the complement: O(n²) instead of O(n³) — Reducing a k-sum problem to repeated two-pointer Two Sums is the classic step from O(n³) to O(n²); module 03 covers it.
8. Saying it out loud: the full 45-second script
"Let me confirm: return two different indices, values may repeat or be negative, n up to 10⁴ and possibly 10⁵, input unsorted. Brute force checks every pair: O(n²), up to 5 × 10⁹ at 10⁵, too slow. For each value I'm searching for its complement, so I'll remember values I've seen in a dict from value to index: one pass, O(n) time, O(n) space. I check before inserting so an element can't pair with itself. If the input were sorted, I'd walk two pointers from the ends instead: O(n) time and O(1) space. Let me code the hash version and test duplicates, a single element, negatives and no solution."
Check yourself
- Which clarifying questions change the code for Two Sum, and how?
- Explain why the two-pointer walk never skips the answer.
- Why is
seen[x] = jafter the check, not before? - Why must random tests check properties rather than exact index pairs?
- What changes when the input is sorted? When you must count all pairs? When memory is tight?
- In a stream design, how does the add-versus-find ratio change the data structure?
Answers
- Reusing an element (store after checking), duplicates (
[3, 3]), returning indices (keep indices when sorting), input size (O(n²) or not), sortedness (two pointers with O(1) space), "no solution" (returnNone). - When the sum is too small, the left value can't reach the target even with the largest remaining partner, so it can't be in any solution; symmetrically for too big. Only impossible values are discarded.
- Storing first would let a value find itself when target = 2x.
- Several valid pairs can exist, and different algorithms may return different ones; validity and existence are what must agree.
- Sorted: two pointers, O(n) time, O(1) space. Counting: store counts of complements, O(n). Memory tight: sort in place and use two pointers, O(n log n) with O(1) extra.
- Many adds: keep counts, scan on find. Many finds: precompute all pair sums on add so find is O(1), at O(n) per add and O(n²) space.