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.
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.
debugger
statement. Do not try to stare at the code and figure out how it works, step through it line by line.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)