Given an array and a target, find two numbers that add up to it. The one-pass hash map turns a nested search into a single question per element: have I seen your complement?
Check the complement before you insert — each element asks one question of the map, then becomes an answer for the future.
Brute force re-scans the array for every element. Flip the search around: as you walk left to right, keep every value you have already seen in a map. For the current x, the partner you need is forced — need = target − x — so the whole problem becomes one map lookup per element.
Step through the scan. Each frame reads one element, asks the map a single question, and either returns the pair or files the element away for later. Type your own array as nums; target.
def twoSum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen: # partner arrived earlier
return [seen[need], i]
seen[x] = i # file away for the future
raise ValueError("no solution")Check-then-store is the whole trick: the lookup happens before the insert, so an element can never pair with itself.
lookup before insertneed is queried before x is stored, so seen[need] is always an earlier index — never i itself, even for [3, 3].return on first hitThe problem guarantees exactly one solution, so the first complement found is the answer; no tie-breaking needed.seen[x] = i overwritesOverwriting is safe: any pair using the older index would already have returned when its complement arrived.2 is stored; 7 needs 2, which the map already holds — return [0, 1] without reading further.
The first 3 is stored before the second arrives, so the complement 3 is found — the edge case that breaks insert-first variants.
I'll walk the array once, keeping a map of values I've seen. For each number I compute the partner it needs, check the map, and only then store it — so the first hit I find is the answer, in linear time.