easy

Two Sum

Find the two numbers in an array that add up to a target value.

1. Define the problem

Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target . You may assume each input has exactly one solution, and you may not use the same element twice. Use a hash map that remembers every value you have already seen and its index, so for each new number you can instantly check whether its matching partner showed up earlier.

Constraints

  • 2 ≤ nums.length ≤ 104
  • -109 ≤ numsi ≤ 109
  • -109 ≤ target ≤ 109
  • Only one valid answer exists

Example

Inputnums = [2, 7, 11, 15], target = 9
Output[0, 1]

Explanation nums0 + nums1 = 2 + 7 = 9, so the answer is the indices [0, 1].

2. Know the words first

In plain terms

Hash map
A lookup table that stores key-value pairs and lets you check "have I seen this before?" in roughly constant time, instead of scanning a list.
3. Visualize the solution

Remember each value seen so far in a hash map

Remember each value seen so far in a hash map
Statusinit

i=0 (value 2). complement = 9 - 2 = 7, not yet in the map. Store 2 -> 0.

What happens in this step

i = 0 (value 2)
complement = target - nums[i] = 9 - 2 = 7
map has no entry for 7

Store nums[0]=2 at index 0 in the map.
Step 1 of 3

Steps to visualize

  1. Walk the array from left to right, one number at a time.
  2. At each number, compute the complement: target minus the current number.
  3. Check the hash map for that complement — if it is there, you found the pair.
  4. Otherwise, store the current number and its index in the hash map and keep going.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Remember each value seen so far in a hash map
Statusinit

i=0 (value 2). complement = 9 - 2 = 7, not yet in the map. Store 2 -> 0.

What happens in this step

i = 0 (value 2)
complement = target - nums[i] = 9 - 2 = 7
map has no entry for 7

Store nums[0]=2 at index 0 in the map.
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function twoSum(nums, target) {
  const seen = new Map();

  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)
6. Test cases

Test cases

InputExpectedCovers
nums = [2, 7, 11, 15], target = 9[0, 1]example from the docstring
nums = [3, 2, 4], target = 6[1, 2]matching pair is not the first two elements
nums = [3, 3], target = 6[0, 1]the two matching numbers are equal values
nums = [1, 2], target = 3[0, 1]smallest valid input, exactly two elements
nums = [-3, 4, 3, 90], target = 0[0, 2]negative and positive numbers summing to zero
nums = [1, 5, 9, 11], target = 20[2, 3]matching pair is the last two elements

Keep reading