# Algorithms 101: TwoSum in JavaScript

*Noob v. LeetCode, episode 1*

A big part of looking for a coding job is being able to pass the technical interview, which usually includes solving algorithms like the ones on LeetCode.com.

What better place to start than the beginning? LeetCode’s very first Algorithms challenge is called TwoSum.

# Brute Force/ Naive

Noobs like me usually find the ‘brute force’ or naive solution first. Those are the solutions that work but take up LOTS of processing time and/or memory. It’s a bit like using a bazooka to swat a fly. It works, but …

Still, you have to start somewhere. Once you get a brute force solution working, you can always refactor.

Enter, bazooka:

If you compare each element in the array to each *other* element in the array, you can check to see if the sum of any two elements equals the target. Then you can then find the index of each of those two elements, put them in an array and return the array.

In other words, you can do this with a nested loop.

`const twoSum = function(nums, target) {`

for (let i = 0; i < nums.length; i++){

for (let j = 0; j < nums.length; j++ ) {

if (nums[i] + nums[j] === target && i !== j){

return [i,j]

}

}

}

}

Let’s unpack that.

If you know what `(let i = 0; i < nums.length; i++)`

means, skip the next few paragraphs!

‘i’ stands for index. By setting ‘i’ to zero, we are saying start with the first element (index = 0); let’s keep going until we reach the end of the array (when i = to the length of the array); and until then, after each iteration, let’s increment ‘i’ by one.

Meanwhile, let’s do the same thing again, but this time we’ll look at the elements at the ‘j’ index.

If we find an element at index ‘i’ and an element at index ‘j’ that add up to the target — *and* if the element we found at index ‘i’ index is not the same element we found at index ‘j’, then we know we have found two separate elements that meet our requirement. Let’s put their indices, ‘i’ and ‘j’ into an array.

It works, but slowly:

Our code may not seem slow in this example, because our array only has four elements. To check each item against each other item in an array with four elements, we have to do 16, or 4² comparisons.

But what if our array had 4,000 elements? Then we’d have to do 4,000² comparisons. In other words, for n elements in our array, we’d have to do n² comparisons. Mathematically speaking, this a Big O notation of n². That is considered very very SLOW.

A better solution would have a Big O notation of n — meaning we would only have to iterate over our array once.

# Better, Smarter, Faster

Let’s re-imagine this problem.

Let’s say you have a large basket of balls, of various weights. You want to find out if any two of them, weighed together, add up to x. In the first solution, we tried every possible combination until we found the right one.

In this next solution, we’re going to start with the same basket of balls (basket #1) plus an empty basket (basket #2) . For every ball in basket #1, we are going to follow these steps:

- Weigh the ball. (Let’s call it the ‘current ball’).
- Subtract the current ball’s weight from the target to get the needed weight— the amount we need another ball to weigh for the current ball and this other ball to be our solution. So if the current ball weighs 2 grams and our target weight is 10 grams, the needed weight is 8 grams.
- Wave a wand over basket #2 and say, ‘Accio, ball that weighs 8 grams!’ If it’s there, it will jump out! (Of course, the very first time we do this, basket #2 will be empty; that’s ok).
- If we don’t find what we’re looking for in basket #2, write the weight of the current ball on the current ball. Then drop it into basket #2.

We do this several times, finding no matches and then …. finally ….

- current ball weighs 8 grams
- Subtract from target weight to get needed weight: 2 grams)
- Wave a wand over basket #2 and call out ‘Accio, ball that weights 2 grams!’— hey, there it is!

4. We’ve found our pair!

# Here’s what that looks like in code:

var twoSum = function(nums, target) {

const previousValues = {};

for (let i = 0; i < nums.length; i++) {

const currentNumber = nums[i];

const neededValue = target - currentNumber;

const index2 = previousValues[neededValue];

if (index2 != null){

return [index2, i];

} else {

previousValues[currentNumber] = i;

// hash[key] = value }

}

}

Again, let’s unpack that.

The empty hash *previousValues* is basket #2; it’s where we drop the balls after we examine them.

*currentNumber*is the current ball (the one at index ‘i’ of our nums array)*neededValue is*needed weight

`const index2 = previousValues[neededValue];`

*index2* is where we found the ball with the needed weight in the original array (*if* that ball exists).

`if (index2 != null){`

return [index2, i];

If *index2* does exist, the matching ball with the needed weight exists, so let’s return the location of the matching ball and the location of the current ball …

} else {

previousValues[currentNumber] = i;

// hash[key] = value}

if *index2* does not exist, then let’s add a key-value pair to *previousValues*, where the key is *currentNumber*, and the value is currentNumber’s index in the original array.

NOTE: since previousValues is a hash, when we look through it for neededValue, we don’t have to iterate. We just have to see if it has a certain value, which it will only have if it has certain key that is equal to the variable *neededValue*. Grabbing values from hashes is way faster (sort of like calling ‘Accio!’ with a magic wand) than iterating through arrays. It has a Big O notation value of n, compared to n² for nested loops)

Sure enough, our method is way faster:

# Many thanks to …

So, noobs, don’t despair. I had very little clue how to tackle this problem at first. I did a lot of Googling, played with a lot of solutions I found, and eventually stumbled across this video, by WebDev Simplified, which helped me understand these concepts!

*Next: Algorithms 101: Reverse a string in JavaScript*

Copyright © Joan Indiana Lyness 2019