Two Sum

The problem

Given a list of integers nums and an integer target, find the two numbers at different positions that add up to target, and return their two positions, counting from 0, in either order. Exactly one such pair exists.

What to write

function solve(nums: number[], target: number): number[]

Input
nums = [2,7,11,15]
target = 9

Output
[0,1]

Input
nums = [3,2,4]
target = 6

Output
[1,2]

Constraints

2–10,000 integers; exactly one distinct-index pair; values and target within ±1,000,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 numbers. Trying every pair is about 50 million additions, so look for a way to handle each number once. Exactly one pair exists, so you can stop as soon as you find it.

2. Hint 2: Ask a smaller question

   Pick one number from the list, say 7, with a target of 9. Which single number would you need to find to finish the job? Where would you look for it?

3. Hint 3: Name the pattern

   For each number you know exactly which partner you need: the target minus that number. A hash map from value to position tells you in one step whether that partner has appeared. This is a hash map lookup. Read the lesson on hash map lookup.

4. Hint 4: State the invariant

   Before you look at a number, the map holds every earlier value with its position. So if the partner is in the map, it sits at an earlier, different position.

5. Hint 5: Sketch the pseudocode

   Start with an empty map. For each position i: let need = target minus the number at i. If need is in the map, return its stored position and i. Otherwise store the number with i.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Scan from left to right and look up target minus the current value. Store each value’s index after checking, so the same element cannot be reused.

The slow way

Try every pair of positions and return the pair whose numbers add up to the target. It is correct, but n numbers make about n × n / 2 pairs, which is 50 million when n is 10,000.

The insight

Once you fix one number of the pair, the other is no longer a guess: it must be the target minus the first. So the question becomes "have I seen this exact value, and where?", which a hash map answers in one step.

Step by step

1. Remember each value seen so far and where it was. The answer needs positions, so a set of values is not enough: the map stores each value together with the position it was found at.
2. Look up the partner this value needs to reach the target. The partner is the target minus the current value. Looking it up in the map checks all the earlier numbers at once.
3. If the partner was seen earlier, the pair is found. The map only holds earlier positions, so the partner's position and the current one are different. That is the pair.
4. Otherwise remember this value and its position. The current value is stored only after the lookup, so a number is never paired with itself.

The same numbered steps are the comments in each solution.

function solve(nums, target) {
  // 1. Remember each value seen so far and where it was
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    // 2. Look up the partner this value needs to reach the target
    const j = seen.get(target - nums[i]);
    // 3. If the partner was seen earlier, the pair is found
    if (j !== undefined) return [j, i];
    // 4. Otherwise remember this value and its position
    seen.set(nums[i], i);
  }
  // The problem promises a pair, so this line is never reached.
  return [];
}

function solve(nums: number[], target: number): number[] {
  // 1. Remember each value seen so far and where it was
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    // 2. Look up the partner this value needs to reach the target
    const j = seen.get(target - nums[i]);
    // 3. If the partner was seen earlier, the pair is found
    if (j !== undefined) return [j, i];
    // 4. Otherwise remember this value and its position
    seen.set(nums[i], i);
  }
  // The problem promises a pair, so this line is never reached.
  return [];
}

def solve(nums, target):
    # 1. Remember each value seen so far and where it was
    seen = {}
    for i, num in enumerate(nums):
        # 2. Look up the partner this value needs to reach the target
        j = seen.get(target - num)
        # 3. If the partner was seen earlier, the pair is found
        if j is not None:
            return [j, i]
        # 4. Otherwise remember this value and its position
        seen[num] = i
    # The problem promises a pair, so this line is never reached.
    return []

Example 2, traced

Input
nums = [3,2,4]
target = 6

Output
[1,2]

Why it works

Take the one pair that works and call its later number b. When the loop reaches b, the earlier number is already in the map, and it is exactly the target minus b, so the lookup finds it. Storing after the lookup keeps a number from pairing with itself.

Time and space

Time O(n) expected, extra space O(n). Each number costs one lookup and one insert. In a hash map both take about one step on average, which is what "expected" means, so the time is O(n). The map can grow to hold almost every number, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Look up the partner before you store the current number. Stored first, a 3 with a target of 6 would find itself and be used twice.
• A stored position of 0 is a real answer, but a bare "if" treats 0 as false. Compare the lookup result with "not found" explicitly.

Pattern

Hash map lookup. Builds on Contains Duplicate.

Keep going