Two Sum JavaScript Solution

The Two Sum problem is a common programming test seen in interviews, and online on sites such as LeetCode, and Codewars. We’ll solve it here using JavaScript.

The reason for the problems popularity is that the solution for solving the TwoSums problem involves a common pattern that you will need in order to solve a large number of programming tests.

The problem typically involves finding if a number exists that is the sum of two integers within an array of unique integers.

The first solution we’ll look at to this problem is using dual for loops like this:

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        answer = target - nums[i]
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[j] === answer) {
                return [i, j]
            }
        }     
    }
};

Now this solution The reason why this solution is not desired is because in it’s worst case it is what is known as N-squared worst case time complexity, meaning the number of operations is about equal to the size of the array of numbers squared.

Not a big deal with the small array in this example, but imagine if there were hundreds of thousands of integers within the number array.  This could take an incredible amount of time.

Nested For Loops Are Rarely The Answer

Something you’ll find with nearly any programming problem is that having nested for loops is rarely ever the solution, so what is the solution in this case? How could this problem be solved with less operations resulting in a possibly much faster solution?

A Faster Solution

The solution in this case is to add the integers in the array into a data structure where they can quickly be looked up by value, in this case the reverse of how they are stored in an array (in the array they can be quickly looked up by index, we want to be able to look up the index with value).

Fortunately, with JavaScript you can quickly do this with a simple JavaScript object, which is also called an associative array or hash table.

Here’s a solution to the TwoSums problem using a JavaScript object:

var twoSum = function(nums, target) {
    previousNums = {}
    for (const [index, num] of nums.entries()) {
        answer = target - num
        if(previousNums !== undefined) {
            return [previousNums, index]
        }
        previousNums[num] = index
    } 
};

This is the accepted solution for the problem, you might notice though that this solution results in more memory usage than the initial solution since we are creating a new object.

Note that in this solution I used a different kind of for loop as in the previous solution, this is a newer syntax introduced in JavaScript ES5, and it could be good to show your answer using a newer syntax.

Is there another solution?

There’s actually another solution where you can sort the array and use binary search to solve this problem, this is a better solution than the initial double for loop and results in a n log N time complexity which is better than N-squared.

Binary search is an article all to itself so we won’t get into this solution here, but it’s something to keep in mind if you’re doing an interview and they ask you how could you solve this without the memory overhead of creating a JavaScript object. 

Note that the binary search solution generally won’t be accepted to solve this problem on testing platforms that test for the speed of your algorithm.

Conclusion

The Two Sums problem is a great problem because understanding the solution will lead you to the correct solution in many programming problems on LeetCode, Codewars, CodeSignal, etc.  and in job interviews (possibly on a whiteboard).  

Understanding how to use hash tables when solving these problems is essential, similar data structures exist or can be created in other program languages.