Leetcode Interview Questions: Two-Sum

Problem statement

Given an array of integers nums[] and an integer target, return indices of the two numbers such that their sum is equal to the target.

Assume that there is exactly one solution, and you are not allowed to use the same element twice. Example: If target is equal to 6 and num[1] = 3, then nums[1] + nums[1] = target is not a solution.

Sample inputs/outputs:

Input: nums = [2,7,11,15], target = 9
Output: [0,1] Because num[0]=2 and num[1]=7, 2+7=9
----------
Input: nums = [2,5,6,7,9], target = 12
Output: [1,3] becasue num[1]=5 and num[3]=7, 5+7 = 12

Solution - dictionary

The dictionary solution works by iterating over the elements of array and calculating the difference between the current and the target number.

Once the difference is calculated, the program will have the current number and the diff - the second number required to reach the desired target sum.

The program will then check whether the diff number was already seen in a previous iteration and if it is, returning the index at which the diff number was found. If the diff number was not previously encountered, the program will store the current index in the dictionary using the current number as the key.

The algorithm (pseudocode)

We iterate over every element of the list, keeping in mind the following variables:

• dictionary <number, number>
• target (number) - the sum we are hoping to find
• i - current index in the list (from 0 to list length - 1)
• current (number) - the value of the current element of the list (value at position i in the list)
• diff (number) = target - current - how far from the target we are (the value of the second number)

On every step of the iteration:

• calculate the diff value by subtracting the current value from the target number
• check whether the diff value was already encountered in a previous iteration by checking if the dictionary contains a key equal to the diff value
  • if the key exists, the first number of the result is the value found at key=index in the dictionary and the second number is the current index
  • if the key does not exist, create an entry in the dictionary using the current number as the key and current index as the value

Javascript code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

const twoSum = (numbers, target) => {
  const dictionary = {};

  for (let i = 0; i < numbers.length; ++i) {
    const current = numbers[i];
    const diff = target - current;

    if (typeof dictionary[diff] !== 'undefined') {
      return [dictionary[diff], i];
    }

    dictionary[current] = i;
  }
  return [];
}

Runtrough

Using the second example with values [2,5,6,7,9] and target=12 our code would work like this

First iteration

On the first iteration, the dictionary is empty and our list index i is at 0. The program calculates the diff by subtracting the current value from the target value. This gives us diff = target - current = 12 - 2 = 10. This means our number pair that sums up to 12 is (2, 10). We already know the index at which the number 2 is found, we just have to check whether we encountered 10 on a previous iteration.

As there is no key in the dictionary with 10 as the key, we “note” the position of our current number and the index at which it can be found. dictionary[2] = 0.

Second iteration

In the second iteration the diff is calculated to 7. As it too does not exist as a key in the dictionary, we add again note the location of the current number 5 in the dictionary dictionary[5] = 1 and proceed to the next iteration.

Third iteration

Here again the diff=6 was not previously encountered, so we note the position and proceed to the next iteration.

Third iteration

On the third iteration, the current number is 7. Subtracting the 7 from the target value, we get diff = 12 - 7 = 5 which exists in the lookup dictionary and references index 1. We can now return the result and exit the function.

The result is [1, 3]. 1 is the index of the number 5 (the number we retrieved from the dictionary) and 3 is the current index.