Two Sum

Problem

Given an array of integers and a target, return indices of the two numbers such that they add up to the target.

Approach

Store previously-seen numbers in a map from value -> index. For each value x, check whether target - x is already in the map.

Complexity

• Time: O(n)
• Space: O(n)

Solution (TypeScript)

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

  for (let i = 0; i < nums.length; i++) {
    const x = nums[i]
    const want = target - x
    const j = seen.get(want)
    if (j !== undefined) return [j, i]
    seen.set(x, i)
  }

  throw new Error('No solution')
}