Solve the Two Sum problem. Given a list of integers and a target, return the indices of the two numbers that add up to the target. What is the optimal complexity?

How to think about it

The best way to start this one is out loud, not in code: “I want to avoid the nested loop. For each number I just need to know whether its complement — target − x — has already appeared, so I’ll keep a dict of what I’ve seen and check it as I go. One pass, O(n).” That sentence tells the interviewer you understand why the hashmap is the answer, not just that it is.

The complement is the whole idea. If x = 7 and target = 9, you need a 2 — and instead of rescanning the array, you ask the dict “have I seen a 2?” in O(1). The one subtlety is order: store each number after checking, so you never pair an element with itself.

A worked example

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i                 # store AFTER the check, never reuse an index
    return []                       # no pair found

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))         # [1, 2] — complement comes later
print(two_sum([3, 3], 6))            # [0, 1] — two separate equal elements
print(two_sum([1, 2, 3], 99))        # []     — no solution

# Trace the seen-dict to watch the single pass work
def two_sum_verbose(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        complement = target - x
        print(f"  i={i}, x={x}, need={complement}, seen={seen}")
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

print("Trace for [2,7,11,15], target=9:")
two_sum_verbose([2, 7, 11, 15], 9)

[0, 1]
[1, 2]
[0, 1]
[]
Trace for [2,7,11,15], target=9:
  i=0, x=2, need=7, seen={}
  i=1, x=7, need=2, seen={2: 0}

Read the trace. At i=0 we look for 7, don’t find it, and remember 2→0. At i=1, x=7 needs 2 — already in seen at index 0 — so we return [0, 1] without ever scanning forward. That’s why a single pass suffices: if two numbers pair up, the earlier one is always already recorded by the time we reach the later one.

A common variant — return the values, not the indices:

def two_sum_values(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return (target - x, x)
        seen.add(x)

This same “have I already seen what I need?” pattern is the seed of three-sum (fix one element, two-sum the rest) and a lot of sliding-window problems. Whenever a question asks “does a value satisfying some relation exist?”, reach for a dict or set.