Complement Lookup: Finding a Pair That Adds Up
You have a gift card worth exactly 50 and a shelf of items with prices. You want two different items that use the card up exactly, and you need to say which two. Trying every pair works, but on a big shelf it is painfully slow. The trick is to stop asking "which pairs add up?" and start asking "what does this item still need?"
The rule
For each value, look up what it still needs: target minus value.
If an item costs 12 and the card is worth 50, its partner must cost exactly 38. That number, 38, is its complement. So walk the shelf once, and for each price check whether its complement has already gone past. A dictionary remembers every price you have passed, together with where it was:
def pair_for(prices, target):
where = {} # price -> position
for i, price in enumerate(prices):
need = target - price
if need in where: # has the partner gone past?
return (where[need], i)
where[price] = i # remember this one for later
return NoneIt is the seen-set from the last lesson with two upgrades: you look up the complement instead of the item itself, and a dictionary stores the position because the answer asks for it. One pass, n steps, and memory for up to n prices.
The idea stretches to any rule where the partner can be worked out from the value alone, such as a pair with a given difference, which the exercise at the end explores. And if the prices were already sorted, the two-pointer section shows a way to find the pair with no dictionary at all.
The shortcut
Say it as a question at each step: "Is my partner already in the book?" If yes, you are done. If no, write yourself into the book and move on. The pair is always found when its second member arrives, because the first one is already written down by then.
Position 0, price 12
Needs 38. The book is empty. Write down 12 at position 0.
Step three is the whole reason for the order of the lines. Looking up before writing down means an item can never pair with itself: one 25 cannot use the 50 card twice. If the shelf held two items priced 25, the second would find the first, which is correct.
Drills
Answer fast — trust the rule.
What does pair_for([8, 14, 3, 11, 6], 17) return?
What does pair_for([25], 50) return?
And pair_for([25, 25], 50)?
Why is where a dictionary rather than a set?
What does the complement lookup cost for n prices?
Remember
- For each value, look up what it still needs: target minus value.
- Shortcut: "is my partner already in the book?" Look up, then write down.
- Trap: writing down before looking up, which lets an item pair with itself.