Two Sum | Programming Challenges

Problem

You are given an array of integers `nums` and an integer `target`. Return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: - Input: nums = [2,7,11,15], target = 9 - Output: [0,1]

Show solution

Solution (TypeScript)

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

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

    const j = seen.get(complement);
    if (j !== undefined) return [j, i];

    seen.set(value, i);
  }

  // Problem guarantees a solution
  throw new Error("No solution");
}

Explanation

We scan the array once while storing each value’s index in a hash map. For the current value `x`, we check whether `target - x` has already been seen. If yes, we found the pair. This is O(n) time and O(n) space.