Two Sum

Problem

Array of integers + a target -> return indices of two numbers that add to target. (Assuming exactly one solution.)

Key Ideas

• Hash map -> O(1) complement lookups.
• Complement = target - current.
• Brute force -> check all pairs.

Tests

• [2, 7, 11, 15], 9 -> [0, 1]
• [-3, 4, 3, 90], 0 -> [0, 2]
• [3, 2, 4], 6 -> [1, 2]
• [1, 2, 3], 7 -> [-1, -1] (no match)

Hash Map, O(n) time / O(n) space

Keep seen integers in a map. For each new one, check if its complement is already there.

function twoSum(integers: number[], target: number) {
  const seen = new Map<number, number>();

  for (let i = 0; i < integers.length; i++) {
    const current = integers[i];
    const complement = target - current;

    if (seen.has(complement)) {
      return [seen.get(complement)!, i] as const;
    }

    seen.set(current, i);
  }

  return [-1, -1] as const;
}

For-of Loop, O(n²) time / O(1) space

Baseline brute force. For each element, check the rest.

function twoSum(integers: number[], target: number) {
  for (const [i, current] of integers.entries()) {
    const complement = target - current;

    if (integers.includes(complement, i + 1)) {
      return [i, integers.indexOf(complement, i + 1)] as const;
    }
  }

  return [-1, -1] as const;
}

Variants

• Return values instead of indices.
• Return all pairs (store in a set).
• Two Sum II (sorted) -> two pointers.
• 3-Sum / k-Sum (sort + two pointers / recursion).
• Streaming data (hash set of complements).
• Closest-to-target variation.

Takeaways

• Map -> fastest, scales well.
• Brute force -> okay for small arrays.