Two Sum

Find two indices whose values add up to the target.

Given an array and a target, return the two indices whose values sum to the target. The key is preserving original indices while finding the complement in one pass.

ArrayHash Table

Pattern fit

Even though the best solution is hash-based, this problem teaches the interview habit of asking whether order or sorting could turn pair search into pointer movement.

Key observation

You are really solving a complement query: for each value x, ask whether target - x has appeared already.

Target complexity

O(n) / O(n)

How to break down the solution cleanly

Scan from left to right and treat each number as a complement query.

Before storing the current number, ask whether target - nums[i] has already appeared.

If it has, return the previous index and the current index immediately.

Otherwise store nums[i] -> i so later values can match against it.

Walk through one example

Example: nums = [2, 7, 11, 15], target = 9.

Read 2 first, store 2 -> 0 because 7 has not appeared yet.

Read 7 next, its complement 2 is already in the map, so answer is [0, 1].

Reference implementation

Python

def twoSum(nums, target):
    seen = {}

    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index

    return []

TypeScript version

TypeScript

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

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index];
    const complement = target - value;

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

    seen.set(value, index);
  }

  return [];
}