The iconic Two Sum in JavaScript

In today’s post, we’re going to be solving the iconic coding challenge, Two Sum. For most people, this problem is fairly trivial but for others, it’s a great place to start and really exemplifies the strengths of certain data structures and we’ll go through a step-by-step solution and analysis within this article.

LeetCode is a great source for coding challenges

Two Sum

‘Given an array of integers nums and an integer target return indices of the two numbers such that they add up to target’ — you may get variations of this problem but in general, it involves a list of integers and you’ll be given a ‘target’ value to reach. The target value is formed by adding 2 of the integers from the list.

Some constraints we will impose to make this problem a little more straightforward are:

• Only one valid answer will exist, e.g. given: [1, 3, 5, 2, 12], 7. Only 5 + 2 will result in 7. An array like [4, 3, 5, 2, 12] will NOT be given as an input as 4 + 3 or 5 + 2 are both valid outputs.
• An integer can only be used once, e.g. given [ 1, 2, 3, 5 ], 6. The only valid output is 5 + 1, 3 cannot be used twice as 3 + 3.

// Some test cases to try out on your own
const twoSum = (array, target) => {
// insert your solution here
}
const arr1 = [3, 4, 5, 6, 7]; 
const target1 = 8;
// should return, [0,2] > 3 + 5 = 8
const arr2 = [34, 23, 35, 24, 2, 7, 11]
const target 2 = 47;
// should return, [1, 3]
const arr3 = [7,7]
const target3 = 14
// should return [0,1]

Give that a try and look below for a brute force, single pass, and two pass approach.

Naive Approach:

The brute force method of this would be to create a nested loop. Fairly straightforward, loop through each element (n) in the given array and create another loop that looks for a value that is equal to target — n . It’ll look something like the below:

const twoSum = (array, target) => {
     for ( let i = 0; i < array.length; i++) {
          for ( let j= i++; i< array.length; j++) {
               if ( array[j] === target - array[i]) return [i, j]               
          };
     };
     return null;
};

If we know anything about nested loops it’s that they have a terrible run time. O(n²), if the input array were to grow to a million element array the runtime would consequently grow exponentially. There is a better solution that can be run in O(n) time.

Two-Pass and Single-Pass approach

The following solutions make use of a hashtable, see my article here for a review on hashtables and their uses. A hashtable is a very useful data structure to use in this problem as insertion, deletion, and searching are all run in O(1) time as long as we know the ‘key’ that we are searching for.

In the two-pass solution, we will be filling up the table with element: index pairs. The second loop will be checking our hashtable if the complement = target — hashtable[i] exists and returning the indices, else we will return num.

const twoSum = (array, target) => {
     const hashtable = {};
    for ( let i = 0; i < array.length; i++) {
       hashtable[nums[i]] = i;   
     };
     for ( let j= 0; j< array.length; j++) {
        let complement = target - array[j]
// The second condition checks for cases like twoSum([7,7], 14) where the indices of similar elements MUST be different
        if ( hashtable.hasOwnProperty(complement) &&      
        hashtable[complement] !== j) {
             return [hashtable[complement], j]
        }
     };
     return null;
};

The use of a hashtable brings down the time complexity to O(2n) which is a huge improvement from the O(n²) we initially started with. The space complexity has increased to O(n) because we are now using the hashtable to store the indices of each element.

The above solution can also be further optimized to a single-pass algorithm as we can check for the complement and add elements and indices to the hashtable in one pass.

const twoSum = (array, target) => {
     const hastable = {};
     for ( let i = 0; i < array.length; i++) {
        let complement = target - array[i];
       
        if ( hashtable.hasOwnProperty(complement)){
          return [hashtable[complement], i]
        }
 
        hashtable[array[i]] = i;   
     };
     
     return null;
};

The above solution is a single-pass and further optimizes our solution’s time complexity to O(n). In my opinion, the two-pass solution was a bit more intuitive and what I came to at first, but we improve our skills with DS and Algo we can optimize our solutions to approach an answer similar to the one above.

As we come to a close to our Data Structures series I will be covering some popular coding problems as well as writing about the new technologies I am delving in to.