# 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^{2})

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)
```