Two Sum

Apply hash-map lookups to solve Two Sum and verify the implementation with test cases.

Try It Yourself

Use the editor below to find two array positions whose values add up to the target. Think about what information should be remembered while scanning from left to right.

Submit your implementation when it passes the examples. A complete solution also handles duplicate values, negative numbers, and pairs far apart in the array.

Two Sum

easyHash Map · Arrays20 minLC 1

Problem

Given an array of integers nums and an integer target, return the indices of the two different elements whose values add up to target.

Exactly one valid answer exists. Return the two indices in increasing order.

Example 1:

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

Output: [0, 1]

Explanation: nums[0] + nums[1] equals 9.

Example 2:

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

Output: [1, 2]

Constraints

2 ≤ nums.length ≤ 10,000
Exactly one valid pair exists.

0 attempts

Solution

Store each value's index as you scan the array. Before storing the current value, calculate the complement needed to reach the target and check whether that complement has already appeared.

Checking first prevents the same element from being used twice. As soon as a complement is found, return its saved index and the current index.

function twoSum(nums, target) {
  const indexByValue = new Map();

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

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

    indexByValue.set(nums[index], index);
  }

  return [];
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	The array is scanned once, with average constant-time map lookups.
Auxiliary space	`O(n)`	The map may store an index for every visited value.