# 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
```