Blog

Two Sum

In Two Sum, we need to find two numbers that add up to a target and return their positions in an array. Candidates have reported being asked this coding interview question at Amazon, Microsoft, and Bloomberg. We'll assume exactly one valid pair of distinct positions exists.

We can start by comparing each value with every later value. Use two loops: hold one position at i, then move j through the positions after it. Check whether nums[i] + nums[j] equals the target and return those two indices when it does.

Target = 10

In the worst case, we check every pair, taking O(n²) time and using O(1) extra space. But what are we looking for in the inner loop? Once we hold 4 and the target is 10, we need 6. We keep searching for that same value as we move j.

Look up the complement

For any current value, its complement is target - value.

target 1064complement

We can keep a hash map of the values and indices we have already visited. When we reach the later member of a valid pair, we can find its earlier partner in that map.

Scan from left to right. Calculate the complement and look it up. If we find it, return the stored index and the current index. Otherwise, store the current value with its index and continue. In our example, we eventually reach 6, look for 4, and find it at index 0.

Look up the partner before storing the current element so that we always use two different positions. Two equal values can still form a pair when they occur at different positions.

Python
def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        partner = target - value
        if partner in seen:
            return [seen[partner], index]
        seen[value] = index
    return None

For an array of length n, we take O(n) expected time and use O(n) extra space, assuming expected constant-time hash-map operations.