4.4.3 — Two Sum

LeetCode 1 · Easy · ★ Blind 75

The problem

Return the indices of the two numbers that add up to target.

nums = [2, 7, 11, 15], target = 9   →  [0, 1]
nums = [3, 2, 4],      target = 6   →  [1, 2]
nums = [3, 3],         target = 6   →  [0, 1]

Exactly one valid answer exists, and you may not use the same element twice.

Note that [3, 3] is legal. The two values may be equal; only the two positions must differ.

The pattern

The brute force checks every pair. But look at what the inner loop is doing: for the number 7 with target 9, it is searching for the value 2 and nothing else.

Do not search for a pair. Fix one number, work out the one partner it needs, and look that partner up.

A two-dimensional search becomes a one-dimensional lookup. The map stores value → index, because you search by value and must return an index.

The solution

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, n in enumerate(nums):
            need = target - n
            if need in seen:
                return [seen[need], i]
            seen[n] = i
        return []

TypeScript

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  return [];
}

One forward pass is enough. Every valid pair has an earlier index and a later index. When the walk reaches the later one, the earlier one is already in the map. So you never need to look ahead — the future comes to you.

Insert after checking, never before. On [3, 3] with target 6: if you store 3 → 0 first and then look for 3, you find the element you are standing on and return [0, 0], which uses one element twice. Check, then insert.

Overwriting a repeated value is harmless. With [3, 5, 3], the second 3 replaces the first in the map. That is fine — one index per value is all you ever need, and by then the earlier index has already had its chance to be found.

Complexity

O(n) time, O(n) space.

Why not sort and use two pointers?

If the array were sorted you could put a pointer at each end and squeeze inward in O(1) space. That is Two Sum II, and it is the opening problem of 4.5.

You cannot do it here because sorting destroys the indices, and indices are what the problem returns. Preserving them means sorting (value, index) pairs, which costs O(n) space again — so you would pay O(n \log n) time for no saving at all.

So: unsorted input and the answer is indices, use a hash map. Sorted input, use two pointers.

Where this goes next

Two Sum is the base case of a family. Every larger member fixes something and reduces to it.

• 3Sum — sort, fix the first element, run two pointers on the rest. 4.5.
• 4Sum — fix two elements, then Two Sum.
• Subarray Sum Equals K — store running prefix sums instead of values, and look up prefix - k. Same move, different thing in the map, and it is the highest-value generalisation here.

The rule: when you need two things satisfying a relation, fix one, solve the relation for the other, and look it up.

Next: 4.4.4 Group Anagrams — the key itself becomes the interesting part.