Two Sum

The problem

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

• Exactly one solution (classic statement)
• Can’t use the same element twice
• Order of the pair doesn’t matter

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]   // 2 + 7 = 9

If you’ve never seen this, welcome. If you’ve seen it fifty times, still nail the pattern — hash map “need = target − x” shows up everywhere.

Brute force (say it, then improve it)

Check every pair. Honest. Slow.

function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [];
}

Time	O(n²)
Space	O(1)

Fine as a 20-second warm-up. Don’t stop here unless n is tiny and the interviewer is bored.

The move: one-pass hash map

As you walk the array, ask: “Have I already seen target - current?” Store value → index as you go.

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 [];
}

Time	O(n) average
Space	O(n)

“Why not sort + two pointers?”

You can — but sorting shuffles indices. You’d keep (value, index) pairs. That works in O(n log n). For the classic “return indices” version, the hash map is the expected flex.

function twoSumSorted(nums: number[], target: number): number[] {
  const indexed = nums.map((value, index) => ({ value, index }));
  indexed.sort((a, b) => a.value - b.value);

  let lo = 0;
  let hi = indexed.length - 1;

  while (lo < hi) {
    const sum = indexed[lo].value + indexed[hi].value;
    if (sum === target) return [indexed[lo].index, indexed[hi].index];
    if (sum < target) lo++;
    else hi--;
  }
  return [];
}

Edge cases worth saying out loud

• Negatives and zeros — still fine
• Duplicates: [3, 3], target = 6 — check before you insert so you don’t pair an element with itself
• “What if no solution?” — clarify constraints; don’t invent APIs mid-interview

Where this shows up

Warm-up energy at Google, Meta, Amazon, Adobe, Uber, and a thousand startups. Follow-ups:

1. All unique pairs (values, not indices)
2. Three Sum
3. Running two-sum over a stream

Related

• Three Sum
• Two Sum II (already sorted)
• Subarray Sum Equals K (prefix sums + map)

Ship the hash map cleanly, talk complexity without mumbling, and move on. Two Sum is a handshake — not the whole interview.