Two Sum — The Lunch Bill Split

Boss 3, the classic

If you've seen any interview prep content anywhere in the last decade, you've heard of this problem. It's called Two Sum and it's the most famous coding interview question on Earth. It's a classic for a good reason. The trick it teaches shows up everywhere after you learn it.

Today you're going to learn that trick by closing out a register.

The story

It's 11pm at the diner. You're counting the till. Everything balances except you're short exactly $23.

You call the manager over. She shrugs. "Happens. Pull the ticket log. If any two meals tonight add up to $23 exactly, just mark it as a combo deal that someone forgot to ring up. Saves the paperwork."

You pull the ticket log. It's a list of prices:

[7, 15, 11, 2, 8, 14, 19, 13]

You need two of those numbers that sum to 23. Fast. The manager is already putting her coat on.

The naive way

Nested loop. Check every pair.

def two_sum_slow(prices, target):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] + prices[j] == target:
                return [i, j]
    return []

For 8 prices, that's at most 28 comparisons. Done before you finish typing.

For 8,000 prices, that's 32 million comparisons. For 80,000, it's 3.2 billion. Your manager has definitely finished her coat.

O(n²). Yet again we want to do better. And yet again, a hash map saves us.

The weapon: complement lookup

Here's the trick. For each price you look at, instead of asking "what pairs with this?", you ask "what would I need to pair with this?"

If the target is 23 and the current price is 15, you need 8. That's the complement. 23 - 15 = 8.

So the question becomes: have I already seen an 8? If yes, those two numbers are the answer. If no, remember this 15 and keep walking.

Walk the list. For each price:

1. Compute the complement (target - price).
2. Check if that complement is already in your hash map.
3. If yes, you found the pair. Return both indices.
4. If no, add the current price to the hash map (value = index) and continue.

One pass. Each step is a constant-time hash lookup plus a constant-time insert. Total O(n).

Let's trace it on [7, 15, 11, 2, 8, 14, 19, 13] with target 23.

Found it in 5 steps. The 15 and the 8 add to 23. The naive approach would have taken up to 28 comparisons on the same input. Hash map wins.

The code

def two_sum(prices: list[int], target: int) -> list[int]:
    seen = {}  # price -> index
    for i, price in enumerate(prices):
        complement = target - price
        if complement in seen:
            return [seen[complement], i]
        seen[price] = i
    return []

Six lines. Read the middle three out loud:

1. What do I need to add to the current price? That's the complement.
2. Have I already seen that number? If yes, I'm done.
3. If not, write this price in my map so a future price can find it.

That's the whole algorithm.

The numbers

Same tradeoff as always. Spend some memory to save a ton of time. For any non-toy input, hash map wins.

Gotchas

1. Storing before checking. Mentioned above. If you do seen[price] = i before the complement check, then for a target of 10 and an input of [5, ...], the first 5 sees itself as its own complement and you return [0, 0]. Wrong. Check before you store.

2. Assuming exactly one answer. The classic Two Sum problem guarantees exactly one valid pair. Real life doesn't. If there can be multiple pairs or none, adjust the return type. Usually interviewers will tell you what to assume.

3. Returning values instead of indices. Read the problem. Some versions want the two numbers, some want their indices. Not the same. Return whatever the problem asks for.

4. Sorted input temptation. If the array is already sorted, you can solve Two Sum with two pointers in O(1) space (no hash map needed). That's actually Boss 2 of the next dungeon. Keep it in mind.

The bigger pattern

Complement lookup is one of the most reused techniques in interviews. The shape is always the same.

You're walking a list, and at each element you ask: "have I already seen the piece that would complete me?"

That exact shape shows up in:

• Two Sum (this one)
• Finding a pair that XORs to a target
• Checking if any two characters combine to a known substring
• Detecting if a subarray sums to zero (the complement becomes a running total)
• Checking for a letter that pairs with another to form a palindrome

The tool is always a hash map, and the question is always "is the thing I need already in here?". Train your brain to reach for this the moment a problem mentions pairs.

Boss down

Register closes at 11:03. Manager gives you a nod. You found the combo: the $15 burger and the $8 fries. Written off. Done.

Next up: Boss 4 — The Sock Drawer. A giant pile of mismatched socks, and your job is to group every sock with the ones that share its exact pattern. You'll meet a sneaky twist on the hash map where the key itself is a sorted or canonical version of each item. Same structure, wildly different use case.

Bring your laundry basket. See you at the dryer.