Two-Sum Challenge in JavaScript

Solving the Two-Sum Problem with JavaScript

A quite popular challenge specially for Developer Interviews is what I stumbled upon in a Leetcode Problem. This is a variation of the classic subset sum problem in computer science.

Problems Statement - Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution-1-My Brute Force Solution

See the Pen 2-Sum-Broot-Force-Blog by Rohan Paul (@rohanpaul) on CodePen.

The above check all the combinations by looping through each element x and find if there is another value that equals to target target−x.

Time complexity : O(n^2)

​​For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2) . The space complexity is constant because it doesn’t need any temporary buffer to store the data.

Solution-2-Slightly Improved version

See the Pen 2-sum-Alt-2-Blog by Rohan Paul (@rohanpaul) on CodePen.

Solution-3-Much Improved Solution with Hash/Object in O(n) time

See the Pen 2-sum-BestO(n)-Solution-Blog by Rohan Paul (@rohanpaul) on CodePen.

Here, under the first for loop, I am doing a numsObject[num] = i which means, I am assigning the given array element value to be the key in the key-value pair of the object / associative-array that I created. And the index-no of that element (i) of that array to be the value in the key-value object.

Then in the second for loop, will check with hasOwnPropery() if the key exists. And here the key that I am looking for will be the will be the compliment (target - x).

In this way, the look up time is reduced from O(n) to O(1) by trading space for speed. A hash table is built to achieve this. It supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully. Since hash table has average access time O(1), and we only access the array once. The time complexity of this solution is O(n). Since we use the hash table as a temporary buffer, at worst case we need additional O(n) storage.

Solution-4-Even more efficient solution

See the Pen 2-sum-best-final-blog by Rohan Paul (@rohanpaul) on CodePen.

While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table with if(numsMap.has(target - array[i])). If it exists, we have found a solution and return immediately return [numsMap.get(target - array[i], i)];.

So, basically we are doing the checking in one-pass.

Time complexity of above : O(n). We traverse the list containing nn elements only once. Each look up in the table costs only O(1) time.

Space complexity :O(n). The extra space required depends on the number of items stored in the hash table, which stores at most nn elements.

In this last solution above, I also used Map rather than use an object literal as a hash-map, given V8 has recently added significant performance improvements to Map and Set making them indispensable for lookups codes. Sometime improving the performance of Map and Set iteration by up to a factor of 11 from Chrome 60 to Chrome 61.

Performance Test with the below script

See the Pen Performance-2Sum-Blog by Rohan Paul (@rohanpaul) on CodePen.

Created a random array with 3000 elements and look at the substantial improvement in each subsequent solution.

Solution-1-Brute Force: 10.418ms

*******************************

Solution-2-Slightly Improved: 7.671ms

*******************************

Solution-3-O(n) time with HashMap: 0.772ms

*******************************

Solution-4-Even more efficient solution: 0.103ms