Javascript Two Number Sum

The two sum algorithm is a common interview question and it's a bit of a trick question. Solving it the right way isn't so obvious and the naive approach many people take is to use the brute force method where they use a nested for loop.

The problem

Give an array of integers nums and an integer target, return the indeces of the two numbers so that they add up to target. If we have an array of nums, nums = [2, 7, 11, 15] and target = 9, we need to return a new array of [0, 1]. This is because nums[0] + nums[1] = 9, we return [0,1].

Brute force method - O(n2)

This is the naive way to solve the problem in which we create a nested for loop. This is far from an ideal solution.

JavaScript
function twoSum(array, target) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === target) {
        return [i, j]
      }
    }
  }
}

twoSum([2, 7, 11, 15], 9)
// [0, 1]

The Performant Way - O(n)

This example uses a hash table and only requires one pass. Take a look at the code first, it might take a second to see what is going on and then we will break it down a bit.

JavaScript
function twoSum(array, target) {
  const nums = {}

  for (let i = 0; i < array.length; i++) {
    const complement = target - array[i]
    if (nums[complement] !== undefined) {
      return [nums[complement], i]
    }
    nums[array[i]] = i
  }
}

twoSum([2, 7, 11, 15], 9)

If the above code is confusing, make sure to run in it the browser, the debugger statement will allow you to step through the twoSum function. So let's re-write the above example and look at our hash table, which is just an associative array. We will first see what our hash table looks like if we loop over the entire array.

One thing that is very important when trying to learn algorithms is using a debugger statement. Do not try to stare at the code and figure out how it works, step through it line by line.
JavaScript
function twoSum(array, target) {
  debugger
  const nums = {}

  for (let i = 0; i < array.length; i++) {
    const complement = target - array[i]
    if (nums[complement] !== undefined) {
      return [nums[complement], i]
    }
    nums[array[i]] = i
  }
}

twoSum([2, 7, 11, 15], 9)
JavaScript
const nums = {}

function twoSum(array, target) {
  for (let i = 0; i < array.length; i++) {
    nums[array[i]] = i
  }
}

twoSum([2, 7, 11, 15], 9)

console.log(nums)
// {2: 0, 7: 1, 11: 2, 15: 3}

This is important to understand as it is the key that allows us to solve this problem with one pass. Each value in the array has been mapped to a key and the value is the index.

In the below code block, on the second iteration of our for loop, our numObj hashtable looks like this: {2: 0}. The complement is 2 since 9 - 7 = 2 and we check if numObj[2] !== undefined and it has a value of 0 so the code inside the if statement is evaluated, and we return [ numObj[2], 1]. The 1 is coming from the i value being in the second iteration and numObj[2] = 0 so we return [0, 1].

If this is confusing, just look at the hashtable and remember how the shape of it looks:

JavaScript
nums = [2, 7, 11, 15]

numObj = {2: 0}

// if there was no if condition numObj would have this shape
numObj = {2: 0, 7: 1, 11: 2, 15: 3}

And here is how the hashtable values are set:

JavaScript
function twoSum(array, target) {
  const nums = {}

  for (let i = 0; i < array.length; i++) {
    const complement = target - array[i]
    if (nums[complement] !== undefined) {
      return [nums[complement], i]
    }
    // nums[2] = 0
    nums[array[i]] = i
  }
}

twoSum([2, 7, 11, 15], 9)