Two Sum

Start from brute force

Try every pair. Two nested loops pick i, then every j > i, and return [i, j] the first time nums[i] + nums[j] == target. Starting j at i + 1 means no element is paired with itself and the indices come out in increasing order, so the answer is always right. The cost is the problem: there are n(n − 1)/2 pairs, so time is O(n²) while extra space is O(1). At the upper constraint of 10⁴ numbers that is 49,995,000 checks when the answer is the last pair. Each outer step rescans the rest of the array to ask one question: is the partner of nums[i] out there?

The approach

For any number x the partner is fixed: it has to be target − x. That turns the pair search into a membership test, “have I already passed target − x?”, and a hash map answers it in O(1) on average. The reference solution walks the array once with enumerate. For each index i and value x it computes need = target - x and checks need in seen. On a hit it returns [seen[need], i]; the stored index is always smaller than i, so the pair is already in increasing order. On a miss it records seen[x] = i and moves on.

The invariant: when the loop reaches index i, seen holds the values of nums[0..i-1] and nothing else. That is why the check comes before the insert. x can only match an earlier element, never itself, while the second 3 in [3, 3] still finds the first. The answer is found at its right-hand element, because its left-hand element is already in the map. The TypeScript twoSum does the same with a Map.

Walk through an example

The first example ends after two steps, so here is nums = [3, 8, 1, 3], target = 6, where the first 3 waits until the end for its partner.

Complexity

Hash map: O(n) time, because each element costs one average-O(1) lookup and at most one insert, and O(n) space, because seen can hold n − 1 entries when the pair is the last two elements. Brute force: O(n²) time for n(n − 1)/2 pair checks and O(1) space. The map buys linear time with linear memory.

Edge cases to test

• nums = [3, 3], target = 6 → [0, 1]. Equal values are different elements; inserting before checking returns [0, 0].
• nums = [3, 2, 4], target = 6 → [1, 2], not [0, 0]: 3 is half the target but appears once, so it must not pair with itself.
• nums = [-3, 4, 3, 90], target = 0 → [0, 2]. Negatives break any shortcut that skips values larger than the target.
• nums = [2, 7, 11, 15], target = 9 → [0, 1]. The partner sits at index 0, so a check written as if seen.get(need): treats it as missing and returns []; test membership with need in seen.
• nums = [8, 1, 2, 4], target = 6 → [2, 3]. The pair is the last two elements, so the map fills to n − 1 entries first: the worst case for time and memory.

Common mistakes

• Pairing an element with itself — check for the complement before inserting the current value.
• Assuming the array is sorted (that is the two-pointer solution) — the hash-map approach needs no ordering.
• Returning the values instead of the indices the problem asks for.
• Rebuilding the “seen” map each iteration instead of carrying it through the single pass.

Follow-ups an interviewer asks next

The array is sorted. Can you drop the hash map?

Yes. Put lo at 0 and hi at the last index. If nums[lo] + nums[hi] is below the target, move lo right; if above, move hi left; stop when it matches. Each move discards an element that cannot be in any remaining pair, because sorted order means no partner left can fix its sum. That is O(n) time and O(1) space.

Return every pair of values that sums to the target, without duplicates.

Keep scanning instead of returning at the first hit. Store seen values in a set, and when target − x is in it, add the normalized pair (min(x, target − x), max(x, target − x)) to a result set so 1 + 5 and 5 + 1 count once. That stays O(n) time and space. Listing every index pair instead can be O(n²) output: an array of all 3s with target 6.

The numbers arrive as a stream, or there are too many for one machine.

The one-pass loop is already an online algorithm: check each arriving value, then insert it, using memory for the distinct values seen so far. To split the work, partition on the key min(x, target − x). Both members of a pair produce the same key, because the partner of target − x is x, so every pair lands in one partition and each worker runs the same map.

Now find three numbers that sum to zero.

Sort once, then fix each element a and run the two-pointer scan for -a on the part to its right. That is O(n²) time and O(1) extra space beyond the sort, and skipping equal neighbors after a match removes duplicate triplets. A hash-map version also reaches O(n²) but makes the deduplication harder to get right.

Where this shows up

“Remember what you’ve seen in a hash map, then answer in O(1)” is one of the most reused patterns in all of engineering — deduplication, hash joins, caches, detecting repeats in a stream, and reconciliation all run on it. Two-sum is the smallest possible instance of trading memory for a linear-time lookup.

Reference solution

def two_sum(nums, target):
    seen = {}                       # value -> index we've already passed
    for i, x in enumerate(nums):
        need = target - x           # the partner that completes the pair
        if need in seen:
            return [seen[need], i]  # found: earlier index first
        seen[x] = i                 # remember x for a future partner
    return []                       # no pair (the prompt promises one exists)


print(two_sum([2, 7, 11, 15], 9))   # -> [0, 1]
print(two_sum([3, 2, 4], 6))        # -> [1, 2]

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index already passed
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];         // partner that completes the pair
    if (seen.has(need)) {
      return [seen.get(need)!, i];         // found: earlier index first
    }
    seen.set(nums[i], i);                   // remember for a future partner
  }
  return [];                                // no pair (prompt promises one)
}

console.log(twoSum([2, 7, 11, 15], 9));     // -> [0, 1]
console.log(twoSum([3, 2, 4], 6));          // -> [1, 2]