Two Number Sum — Part II

In Part I of the “Two Number Sum” problem series, my partner soniasusanto took you through the brute force solution as well as an optimized approach that uses sorting and pointers to improve the time complexity.

To reiterate the problem, we are writing a function that takes an array of distinct integers and an integer that represents the target sum and returns an array of two numbers from the input array if they add up to the target sum. If there are no two numbers that add up to the target sum, the function should return an empty array. Please refer to Part I for more detail.

Another way we can approach this problem is as a simple math equation, where each of the elements of the array (aka “currentNum”) accessed via iterating through the array represents one variable (X) and other unknown variable (Y) sums up to the “targetSum”:

X + Y = targetSum 
or
currentNum + Y = targetSum

And given the “targetSum” and “currentNum,” we are able to look for the other variable (Y):

Y = targetSum — currentNum

With this in mind, we can use a for loop to iterate through the input array to access each of the numbers and check to see if the input array includes the the difference between the “targetSum” and the “currentNum” in the iteration (aka variable Y).

If we find that the array includes the difference, then we will push both the “currentNum” and the difference to our result array and break out of the for loop to return it.

Although this solves the problem and got us thinking about the problem in a slightly different way, this solution is not optimized for time. Because the array.includes() method iterates through each of the elements under the hood and we are also using a for loop to iterate through the input array to access each of the numbers, the final time complexity of this solution would be O(n²).

So how can we optimize this solution to get a better computation speed? For this problem, we can utilize a hash table to help optimize our time!

Before we jump to the solution, here is a quick overview on hash tables:

1) Hash table is a data structure where we can store key-value pairs

2) Under the hood, hash table is built on top of an array that uses hash technique to generate a “unique” index for each of the key where its value will be stored

3) We can access the value via the key that maps to a “unique” index, so that we can perform various operations (such as lookup, insertion, deletion, etc.) in constant time

4) In Javascript, we have a built-in hash table that is directly supported; they are called objects!

Now, back to the solution. To reduce the amount of loops, and thereby optimizing time complexity, we can store every number from the input array in a hash table so that we can access the numbers in constant time via the hash table.

We can do this by iterating through the input array, and at every “currentNum”, we solve for the difference (“targetSum — currentNum”). We can check whether the difference is in the hash table, and if it is not, then we will store the “currentNum” to the hash table. If the difference is in the hash table, then we will return the difference and the “currentNum” as we’ve found the two values that add up to the “targetSum”.

Let’s see this in code:

In terms of the time complexity, by utilizing the hash table, we successfully reduce it to O(n). However, as we are creating a hash table within our function, the space complexity for this solution would be O(n).

In conclusion, there are many ways to approach an algorithm and different approaches have varying time/space implications. To see all the solutions discussed in our two-part series on “Two Number Sum”, please check out our github repo.

Next up, we will be tackling problems “Three Number Sum” and “Four Number Sum” leveraging what we learned here in utilizing data structures or sorting algorithms (see Part 1) to optimize for time and space complexities.