Tackling the Two Number Sum Algorithm

One of the most popular coding questions involves the two number sum. “Given an non-empty array of distinct integers and a target sum, find two numbers in the array that add up to the target sum.” Or it’s possible that no numbers add up to the target sum. So for example, given the input: [[3, 5, -4, 8, 11, 1, -1, 6] and a target sum of 10, an output could be [-1, 11].

We’re going to begin by creating a hash to store the numbers we have already visited in our loop. That way, we can access them easily if they’ve already been visited, or we can easily skip over them if we know they aren’t the match for our current number.

Next, we’ll begin looping over our array with a For… Of Loop. If you are not familiar with this kind of loop, I urge you to look at some documentation. For each item we iterate over, we’ll be calculating what the potential match may be. We can do this by subtracting that number from the targetSum passed into the function.

Now that we know what number we’re on and what its potential match may be, let’s see if that potential match is already in our hash. If it is, then we we’ll have solved the problem and can return an array of the number and the potential match.

However, if it is not in our nums hash, then we’ll want to add our current number to the hash. So let’s create an else statement that takes care of that. I’m going to set my number equal to a value of “true,” but you can really set it to anything.

Lastly, we need a base case. If there are absolutely no pairs in the array that add up to the targetSum, then we want to return an empty array. So let’s return an empty array outside of our For loop to account for this.

And there you have it! Since this problem will only run as many times as the length of the array, it has a linear time complexity: O(n).