Card 06/ 08
Recording an Item Before Looking Up Its Complement
Store first and look up second, and an item can pair with itself: 6 finds 6 when the target is 12.
In a one-pass pair search, each item must be looked up before it is recorded, because recording it first lets the item find itself. A search for two values adding up to 12 in 6 2 9 shows it. No two different values sum to 12, but a version that stores 6 and then asks whether 12 − 6 = 6 is in the map finds the 6 it has just stored, and reports index 0 paired with index 0. The listing runs both orders on that input and on 6 6, where a pair does exist.
def pair_record_first(values: list[int], target: int) -> tuple[int, int] | None:
seen: dict[int, int] = {}
for i, value in enumerate(values):
seen[value] = i
if target - value in seen:
return seen[target - value], i
return None
def pair_look_up_first(values: list[int], target: int) -> tuple[int, int] | None:
seen: dict[int, int] = {}
for i, value in enumerate(values):
if target - value in seen:
return seen[target - value], i
seen[value] = i
return None
for values in ([6, 2, 9], [6, 6]):
print(values, "record first:", pair_record_first(values, 12))
print(values, "look up first:", pair_look_up_first(values, 12))[6, 2, 9] record first: (0, 0)
[6, 2, 9] look up first: None
[6, 6] record first: (0, 0)
[6, 6] look up first: (0, 1)Looking up first keeps the invariant that the map holds only items before the current one, so the current item can never be its own partner. The same order still handles two equal values that do form a pair: on 6 6, the second 6 finds the first and reports indices 0 and 1. Recording first gets 6 6 wrong too, more quietly: it reports 0 and 0, an answer of the right shape that names one item twice.
The swapped order fails only when some value is exactly half the target, which is why tests on random inputs often miss it. An edge-case test holding target ÷ 2 once, and another holding it twice, catches it in both directions.
← → move through sections and cards