“Know how to solve every problem that has been solved.”“What I cannot create, I do not understand.”— Richard Feynman
Two Sum
Interview Prep
Warm-upArrays & Hashingarrayshashmap
The problem
Given an array of integers nums and a target sum, return
the indices of the two numbers that add up to the target. Each input
has exactly one solution, and you can return the indices in any order.
The lesson: hashmaps exist
You know, if I had to sum up this problem (pun partially intended),
I would describe it as an exercise in — hey, did you know that
hashmaps exist? Before I learned this problem I don't think I
really knew what a hashmap was. I just knew
python-dictionary-lets-me-index-stuff-with-words-instead-of-numbers.
Brute force
Try every pair: not a bad solution if you don't know hashmaps
exist. Seriously, I worked mostly with arrays and thought O(n²) is
all you're getting, unless I prove O(n) = O(n²). And no, I'm not
secretly trying to prove that theorem. It didn't look too
promising after I tried proving the lemma that 2 = 4, and that
1 = 1 still holds.
def two_sum(nums: list[int], target: int) -> list[int]: 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 []
Time O(n²). Space O(1).
For n = 10⁵ this is already past
most online-judge time limits.
Optimal
Walk the array once. At each index i, compute what the
complement would be (target - nums[i]). If we've seen
that complement before, we have our pair. If not, remember the
current value for someone later to find.
def two_sum(nums: list[int], target: int) -> list[int]: seen: dict[int, int] = {} # value -> index for i, x in enumerate(nums): complement = target - x if complement in seen: return [seen[complement], i] seen[x] = i return []
Time O(n) — one pass.
Space O(n) — the hashmap.
Walkthrough
nums = [2, 7, 11, 15], target = 9i = 0 x = 2 complement = 7 seen = {} → not found, store 2:0i = 1 x = 7 complement = 2 seen = {2: 0} → hit, return [0, 1]
Read the loop in your head: at each step ask "is the complement
already there?" before remembering the current value. Order matters —
storing first would let an element pair with itself.
Edge cases
Duplicates that sum to the target.nums = [3, 3], target = 6. The first 3 goes in the
hashmap; the second 3 finds it as its own complement. Returns
[0, 1].
No valid pair. The problem guarantees one exists
in interviews, but a defensive return is still good. The empty
list is a fine sentinel.
Negative numbers and zero. The hashmap handles
them transparently; nothing about the algorithm assumes positivity.
Try First
Each prompt asks a checkable question about the working code or math
above — predict an output, derive a sign, state an invariant, find a
bug. Commit to an answer before clicking "reveal." That commitment is
the whole point: if your answer matched, you understand the piece you
were looking at; if it didn't, that's the part worth re-reading.
invariant
At the top of iteration i in the optimal solution — before
the if-check runs — state precisely what seen contains.
Be specific about which prefix of nums is represented and
which direction the mapping goes.
answer
At the top of iteration i, seen is the
mapping {nums[k]: k for k in range(i) if not yet duplicated}
— that is, for each index k < i, the entry
nums[k] -> k is present unless nums[k]
appeared earlier and got overwritten. So seen answers
"for each value seen so far, where was its last occurrence?" The "last
occurrence" detail matters: if nums = [3, 5, 3] reaches
iteration 2, seen[3] = 0 got overwritten to
seen[3] = 2 at iteration 2 — wait, no, that overwrite
hasn't happened yet at the top of iteration 2; it happens on the
store line. Re-read the code carefully and you'll see the lookup
always runs against seen with strictly earlier
indices.
predict
Predict two_sum([3, 3, 3, 3], 6). There are six unordered
pairs of indices that all satisfy the constraint. Which one does the
function return, and why that one?
answer
Returns [0, 1]. The first 3 (at index 0) goes into
seen. At index 1, the lookup for the complement
6 - 3 = 3 finds index 0, and the function returns
immediately. The remaining 3s at indices 2 and 3 are never reached.
The early return is doing real work: the function is a "find any
valid pair" solver, not an "enumerate all valid pairs" one. If you
wanted all of them you'd remove the return and keep walking — but
notice that the natural extension finds pairs by index, not
by value, so the six index-pairs from this input would all be
returned even though "as a value-pair" they're the same.
find the bug
I changed complement = target - x to
complement = x - target. The code still runs and still
returns lists of integers. Find an input where it now returns a pair
whose values do not sum to target — and explain why the
if complement in seen check failed to catch it.
hint
Lookups in the dict happen against the BUGGY complement. The check
is comparing the wrong thing — but to itself, consistently. When can
the buggy complement accidentally equal some previously-seen value?
answer
Try two_sum([5, 1, 9, 2], 4). With the buggy formula,
complement = x - target:
i=0, x=5: comp = 5 - 4 = 1. seen empty, store {5: 0}.
i=1, x=1: comp = 1 - 4 = -3. Not in seen. Store {5: 0, 1: 1}.
But nums[0] + nums[2] = 5 + 9 = 14, not 4. The buggy
check fired because the complement happened to coincide with a real
stored value, even though that coincidence has nothing to do with
the target. The if-check trusts the formula. Bugs in the formula
propagate silently through the data structure because the data
structure has no independent semantic check. This is why "verify
on a known case" is non-negotiable for any function involving
algebraic relationships.
what if
Now imagine the input arrives as a stream: you see nums[0],
then nums[1], then so on, and at any point the caller may
ask "has any pair seen so far summed to target?". What state does the
function need to maintain to answer in O(1) per query? What state is
it OK to drop?
answer
Maintain seen as a set (not even a dict, since you don't
need indices for the yes/no question) AND a single boolean
found. On each new element x: if
target - x in seen, set found = True;
regardless, seen.add(x). The query "has any pair summed
to target?" returns found — answered in O(1).
Notice what you can drop: order of arrivals, indices, values you've
already used to match. The set only remembers "has this
value been seen?" — a one-bit summary per value. This is the
streaming algorithm version of the hashmap two_sum, and it's how
you'd implement two-sum-on-an-infinite-stream. Two-sum-on-a-stream-with-a-memory-budget
is harder; you'd need approximate set membership (Bloom filters)
and you'd accept a false-positive rate. There's a whole subfield
of streaming algorithms built on these compromises.
Hack This
The code above works. Don't reinvent it — pull it into an editor, run it, and
try the modifications below. Each one is small. Each one will change the behavior
in a specific way; the question is which way.
trivial
Swap target - x for target / x in the optimal
version (pretend integer division works out — use positive ints and a
target that divides cleanly). You've turned Two Sum into Two Product.
The structural question: addition is its own inverse (the complement of
x is target - x); multiplication's inverse is
division. The hashmap pattern works for any operation whose inverse you
can compute. Construct an input where the SUM-of-pairs and the
PRODUCT-of-pairs interpretations return different index pairs, and use
it as a sanity check that the "operation-agnostic" hashmap trick really
is operation-agnostic.
hint
Try arrays where some pair adds to T AND a different
pair multiplies to T. [1, 2, 3, 6] with
T = 6 works — 2 + 4 = 6 isn't available
but 1 + 5... actually try [2, 3, 4] with
T = 6: 2 + 4 = 6 (Two Sum) versus
2 * 3 = 6 (Two Product).
trivial
Move seen[x] = i to run before the
if complement in seen check. The walkthrough warns that
"order matters." Confirm by finding the smallest input where the
reordered version returns a pair the original explicitly rejects.
Then state, in one sentence, the invariant the original code maintains
that the reordered version violates.
hint
The dangerous case is when an element is its own complement. What's
the smallest (nums, target) where target = 2 · nums[i]
for some index i?
trivial
Replace the dict with a set. Try to keep returning indices. You'll
find the function can no longer answer the original question — a set
remembers that a value was seen, not where. What is
the dict actually carrying that a set isn't? Now: what's the minimum
change to the function's signature that makes the set-based version
correct and meaningful?
hint
Think of the dict as bundling two pieces of information: a membership
check (set-like) and an index lookup (dict-only). Drop the index
lookup and your output has to also drop the index dimension —
return the matched values, not the matched indices.
small
Modify the function to return both the answer AND the final
seen dict. Now use that returned dict to instantly answer
a follow-up question: "given the same input and target, what's the
SECOND pair that sums to target (lexicographically by left index)?"
Does the dict alone suffice, or do you need to re-process the array?
Use this to articulate exactly what information the original function
throws away on exit.
hint
The dict tells you "what values have been seen, and where most
recently." It doesn't tell you about pairs you'd have found if you'd
kept walking past the early return. To enumerate ALL pairs you
still need a linear pass — but the dict is half of that work
already done. What's left is a single sweep where, for each
nums[i], you check if target - nums[i]
was seen at any index other than i.
small
Write a three_sum(nums, target) that reuses two_sum
as a subroutine — don't write any new dictionary logic. The reduction:
for each candidate first element nums[i], call
two_sum(nums[i+1:], target - nums[i]). Then ask the harder
question: this reduction gives you O(n²) total time. The dedicated
three_sum algorithms in the wild are also O(n²). Why doesn't the
reduction make three_sum somehow worse? And what does this tell you
about the cost of building a generic k_sum?
hint
Each call to two_sum is O(n). You make O(n) of those
calls. n · n = n². For k_sum: each level adds a factor of n. So
k_sum is O(n^(k-1)) regardless of how cleverly you stack the
reductions — until you hit known lower bounds.
small
Bug-hunt in the brute force: change range(i + 1, n) to
range(i, n). The function still runs. Find an input
where the new version returns a pair the problem statement forbids,
then state — in terms of the original constraint, not in terms of the
bug — what just went wrong.
hint
The constraint says i ≠ j. The change permits
i = j. So the failing inputs are exactly the ones where
an element is its own complement under doubling.
Related
Two Sum II — Sorted Array. Sorted inputs unlock
an O(1)-space two-pointer sweep. Different pattern, same problem
shape.
Three Sum. Sort first, then for each anchor run
a two-pointer scan over the rest. Builds directly on this pattern.
4 Sum. Two anchors plus the same two-pointer
inner. The pattern keeps composing.