Coding Interview

A standard warm-up question. Given a list of integers and a target value, return the positions of the two entries that add up to the target. Exactly one pair works, and no entry may be used twice.

With nums = [2, 7, 11, 15] and target = 9 the answer is [0, 1], since 2 + 7 = 9.

The obvious solution compares every pair, which costs O(n²):

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

A single pass with a dictionary brings it down to O(n). For each value, ask whether the complement has already been seen:

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

The second version is the one worth remembering, because the trick generalises: when a nested loop is searching for something it has already walked past, store what you have seen and trade memory for the scan.