Two Sum

Difficulty: Easy

You're given a list of numbers and a target number. Find two different numbers in the list that add up exactly to the target, and return their positions (indexes) in the list.

You can assume there's always exactly one valid pair, and you can't use the same element twice.

Examples

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

nums[0] + nums[1] = 2 + 7 = 9.

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

nums[1] + nums[2] = 2 + 4 = 6.

Input: nums = [3, 3], target = 6
Output: [0, 1]

Constraints

2 <= nums.length <= 10^4
-10^9 <= nums[i], target <= 10^9
Exactly one valid answer exists.

Approach

The most direct way to solve this is to check every possible pair of numbers and see if any pair adds up to the target. That works, but it means comparing each number against every other number - a lot of repeated work.

A faster way: as you walk through the list once, ask "what number would I need to see, together with the one I'm looking at right now, to reach the target?" If you've already seen that number, you're done. A hash table lets you check "have I seen this value already" instantly, turning the problem into a single pass through the list.

Solutions

Brute Force - Check Every Pair

Try every pair of numbers and check if they add up to the target. It's the most obvious solution, but it looks at every pair, so it does far more work than necessary as the list grows.

function twoSum(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)

Optimal - Hash Map

Walk through the list once. For each number, check whether the value needed to complete the pair (target - currentNumber) has already been seen. A Map lets you check that instantly, while remembering every number's position as you go.

function twoSum(nums, target) {
  const seen = new Map(); // value -> index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }

  return [];
}

Time: O(n) · Space: O(n)