TL;DR: One pass with a hashmap of value to index. Check for the complement before inserting the current value, so duplicates like [3,3] work.
How to approach it Don't jump to code. State the brute force in one sentence ("nested loops, O(n²)"), then immediately offer the better idea: for each number, ask "have I already seen its complement?" That question is a hashmap lookup. Clarify two things out loud: are there duplicates, and is exactly one solution guaranteed? Those answers decide whether you store one index or a list per value.
A strong answer One pass, storing each value's index as you go. Checking before inserting handles duplicates like [3, 3] with target 6 correctly:
def two_sum(nums: list[int], target: int) -> list[int] | None:
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 None # no pair exists
Narrate the invariant while you write: "seen holds every value strictly to my left, so I never pair an element with itself." O(n) time, O(n) space.
If the invariant feels abstract, trace it once on nums = [11, 2, 15, 7], target 9 (traced by running the code, and worth doing on the whiteboard at speed):
| i | x | complement | in seen? | action |
|---|---|---|---|---|
| 0 | 11 | -2 | no | insert 11 -> 0 |
| 1 | 2 | 7 | no | insert 2 -> 1 |
| 2 | 15 | -6 | no | insert 15 -> 2 |
| 3 | 7 | 2 | yes, index 1 | return [1, 3] |
Each element gets exactly one lookup and at most one insert, which is where O(n) comes from, and the check-then-insert order is visible in the trace: 7 finds the 2 that was inserted two steps earlier, never itself.
Then add tests unprompted. This is what separates a practical-coding pass from a bare LeetCode answer:
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1] # duplicates
assert two_sum([-1, 4, -3], -4) == [0, 2] # negatives
assert two_sum([5], 10) is None # no pair
assert two_sum([], 0) is None # empty input
The three approaches worth naming, and when each one wins:
| Approach | Time | Space | Reach for it when |
|---|---|---|---|
| Brute force, nested loops | O(n²) | O(1) | Only to state the baseline out loud before improving it |
| Hashmap, one pass | O(n) | O(n) | Default. Input is unsorted and you need the indices |
| Two pointers | O(n) | O(1) | Input is already sorted (O(n log n) if you sort first, which scrambles indices) |
One more reason interviewers open with this, worth knowing if you are coming from outside algorithm-interview culture: the hashmap move here is not a puzzle trick, it is the single most reused pattern in data work. "Have I seen this key before, in O(1)?" is deduplication by event ID, it is the probe side of a hash join, it is the idempotency check in a webhook consumer, it is sessionizing a click stream. The interviewer is checking that trading O(n) memory for O(1) lookups is reflexive for you, because at a customer site the same reflex is the difference between a pipeline that joins two feeds in one pass and one that quadratically rescans. Saying a short version of that connection out loud turns a warm-up into a signal.
What interviewers probe next Three standard follow-ups. (1) Sorted input? Two pointers from both ends, O(1) space, but note that sorting first to use it costs O(n log n) and scrambles indices, so you'd sort (value, index) pairs. (2) Return all pairs? Now duplicates matter: store dict[int, list[int]] and decide with the interviewer whether (i, j) and (j, i) count once. (3) Stream too large for memory? If the value range is bounded, a count array; otherwise discuss approximate structures. They're checking whether you adapt rather than recite.
Common mistakes Inserting into the map before checking, which pairs an element with itself when target == 2 * x. Returning values instead of the indices the problem asked for. Saying "use a set" then realizing too late you needed indices. Silence while coding: FDE loops explicitly grade narration, and a 10-line solution delivered mutely scores worse than the same solution explained. Finally, skipping tests: on practical screens, writing five asserts unprompted is the cheapest signal you'll ship reliable code at a customer site.