Lesson 08: Stop Using Nested Loops: Solve the Two Sum Problem in One Pass

Master the Two Sum Coding Interview Problem Using a Hash Map — Learn How to Find Two Product Prices That Add Up to a Target in O(n) Time, Avoid Unnecessary Comparisons, and Explain the Algorithm Like an Experienced Software Engineer.

The interview insight: The number you need might already be stored. Instead of searching for it repeatedly, remember what you've seen.

"Find two numbers that add up to a target." It is one of the most common interview questions. The slow answer uses two loops. The fast answer uses one loop and a dict. Here is how it works, and the two traps that break it.

The problem at Varastra

Varastra is an online store for Indian ethnic wear. A customer has a gift voucher. She wants to spend all of it on exactly two items. Varastra's page should show her one pair of items whose prices add up to the voucher value.

Say the prices are [2, 7, 11, 15] and the voucher is 9. The answer is the items at index 0 and index 1, because 2 + 7 = 9.

Tara, a new intern, writes the first idea that comes to mind. Sam, a senior engineer, asks, "What does it cost?" This time, Tara is ready. She says the cost out loud before she writes any code. (The story is made up.)

The brute force answer

Try every pair. If a pair adds up to the target, return its positions.

def pair_brute(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 None

It is correct. The cost is O(n²) time and O(1) extra space, because it compares each item with every item after it.

Here is how slow it gets in the worst case, when no pair exists.

These numbers were measured on one machine. They will differ on yours. The shape will not: brute force grows about four times each time n doubles.

The key idea: ask for the partner

Here is the trick. For each price, do not ask "which other price works with me?" Ask: "What price would complete the total?"

If the target is 9 and the current price is 2, the partner must be 7. If you already saw a 7, you are done.

So remember every price you have passed, and where you saw it. A dict does that job. The key is the price. The value is its index.

def pair_with_total(prices, target):
    seen = {}                                 # price -> index where first seen
    for j, price in enumerate(prices):
        need = target - price
        if need in seen:
            return seen[need], j
        if price not in seen:
            seen[price] = j
    return None

Pause and predict

Before you read the walkthrough: for [2, 7, 11, 15] and a target of 9, how many prices does the fast code look at?

Answer: Two. It stops at 7, because the partner 2 is already in the map.

Walk through the diagram

The diagram traces [2, 7, 11, 15] with a target of 9.

Step 1: j = 0, price 2.

• need = 9 − 2 = 7.
• Is 7 in seen? No.
• Add 2 to seen. Now seen = {2: 0}.

Step 2: j = 1, price 7.

• need = 9 − 7 = 2.
• Is 2 in seen? Yes, at index 0.
• Return (0, 1).

We stopped after two steps. We never looked at 11 or 15.

print(pair_with_total([2, 7, 11, 15], 9))   # (0, 1)

Try it

Call pair_with_total([2, 7, 11, 15], 26), then try a target of 100. What do you expect?

26 gives (2, 3), because 11 + 15 = 26. The code reads four prices this time. 100 gives None, because no pair adds up to it.

The cost

One pass over the list. Each price needs one dict check and one dict add. So the time is O(n) on average. The dict can hold every price, so the extra space is O(n).

The brute force version had O(n²) time and O(1) space. This one has O(n) time and O(n) space. It is a clear trade: we spend memory to save time.

Say it like this in an interview:

"I will use O(n) extra space to bring the time from O(n²) down to O(n)."

Trap 1: an item pairing with itself

Say the voucher is 6, and the list has one item priced 3. Can the code return the same item twice? It must not. The answer should be None.

The code avoids this by one rule: check the map before you add the current price. So when the code looks for the partner, the current item is not in the map yet.

print(pair_with_total([3], 6))   # None

If you swap the order and add first, the item finds itself. The code would return (0, 0), which is wrong.

Trap 2: two equal prices

Now say the list is [3, 3] and the target is 6. Two different items cost 3 each. The answer should be (0, 1).

print(pair_with_total([3, 3], 6))   # (0, 1)

The first 3 is stored in the map. The second 3 looks for a partner of 3 and finds the first. It works.

Notice the line if price not in seen. It keeps the first position of each price. Without it, a later equal price could replace the earlier index, and the result could point to the wrong item.

Test it against the slow version

The slow version is easy to trust. So use it to check the fast one.

import random

assert pair_with_total([2, 7, 11, 15], 9) == (0, 1)
assert pair_with_total([3], 6) is None
assert pair_with_total([3, 3], 6) == (0, 1)
assert pair_with_total([], 5) is None

for _ in range(500):
    prices = [random.randint(1, 20) for _ in range(random.randint(0, 10))]
    target = random.randint(2, 40)
    fast = pair_with_total(prices, target)
    slow = pair_brute(prices, target)
    assert (fast is None) == (slow is None)
    if fast:
        i, j = fast
        assert i != j and prices[i] + prices[j] == target

print("all tests pass")

The two methods may return different pairs when more than one pair exists. Both are correct. The test only checks that both agree on whether a pair exists, and that the fast answer is valid.

How to spot this pattern

1. The problem says "find two items that add up to a target." Think of a dict from what you saw to where you saw it.
2. For each item, you can work out exactly what its partner must be. That is the "complement."
3. Brute force checks every pair. Whenever you see that, ask if a map can find the partner in one look.

The same idea works for differences ("find two items that differ by k") and for pairs that match in some other way. If you can compute the partner, look it up.

Takeaway: For each item, ask what partner you need. Check the map first, then add the item. One pass, O(n) time on average, O(n) extra space.