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(n²)

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

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.

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.

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)

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:

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:

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)