Solving The Two-Sum Problem in Javascript, Three Ways

Published by ∞ Level Up Coding
Featured by ★ Medium Curated

This Github repo contains my completed code for all three solution models.

What is the Two-Sum Problem?

“Given an array of integers and a target number, return the two integers that add up to the target number”

Notes:

The desired result can be returned in a few different forms — I’ve seen queries ask either for the indices of the addends (aka their locations in the array), or for the addends themselves.

Additionally, some challenges are structured so that only one pair of numbers will add up to the sum.

In my solutions, I will be returning all discrete successful addend pairs.

I will briefly address approaches for adapting my solutions to return a single addend pair or array indices rather than addends themselves.

I will use the array [2, 3, 4, 3, 6, 7], and the sum integer 6 to test all solutions.

1: BRUTE FORCE

For my first solution, I’m not prioritizing elegance or performance, merely attempting to hack a working solution. Once I have some working raw material and an initial understanding of the mechanics of finding my desired numbers, then I can play with my solution to address time complexity, etc.

As I know I may need to find multiple correct number combinations, I start with an empty array, and plan to pass my successful number combos into it, then return the array of number combos.

If it were established at the beginning of a challenge that each sum + array combo could only have one successful solution, I could skip this step and instead return the correct addends once found.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

  // find addends
  // pass them into nums array for storage

   return nums
}

First, I need to find the successful combos.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

      for(let x in array){
        for(let y in array){
            // see if array[x] + array[y] === sum
            // save successful combos to nums array
        }
      }     
   return nums
}

I start by creating two loops, allowing me to iterate through every combination of numbers in the array. Now I can test the combos to see if any of them add up to sum.

let bruteForceTwoSum = (array, sum) => {

  let nums = []

      for(let x in array){
        for(let y in array){

          if (array[x] + array[y] === sum){
            nums.push([array[x], array[y]])
          }

        }
      }     
   return nums
}

If they do, I want to save them in my container array, which I’ll return after closing out my loops.

If I wanted the indices instead of the number elements themselves, I could instead push x & y to the nums array.

When run in the console, this function returns:

let array = [2, 3, 4, 3, 6, 7]
let sum = 6

bruteForceTwoSum(array, sum)
0: (2) [2, 4]
1: (2) [3, 3]
2: (2) [3, 3]
3: (2) [4, 2]
4: (2) [3, 3]
5: (2) [3, 3]

✔️ This function is finding and returning both [2, 4] and [3, 3].

✖️ It’s also returning them multiple times each. Not what we want.

I could try to check the nums array before pushing new number combos in, but the nested array format I’ve used makes this a hassle.

Note: It is perfectly reasonable to check nums.flat(Infinite) for the current elements, but I chose a slightly less computationally expensive option.

function bruteForceTwoSum(array, sum){
    let nums = []

    let prevNums = []

    for(let x in array){
        for(let y in array){
            if (array[x] + array[y] === sum){
                if(!!nums.length){ 
                    if (!prevNums.includes(array[x]) && !prevNums.includes(array[y])) {
                        prevNums.push(array[x])
                        nums.push([array[x], array[y]])
                    } 
                } else {
                    nums.push([array[x], array[y]])
                    prevNums.push(array[x])
                }
            }
        }
    }
   return nums
}

I’ve added an additional array prevNums for the sole purpose of storing found numbers, and can now check if a number has already been found & added before pushing it into nums. I only do this if nums is not empty.

What does this return?

let array = [2, 3, 4, 3, 6, 7]
let sum = 6
bruteForceTwoSum(array, sum)

0: (2) [2, 4]
1: (2) [3, 3]

Great! This is exactly the result I want. 🌟

2: BINARY SEARCH

Okay, so I have my first layer. I can find the combinations in an array that add up to a given sum, and return them in a clean, readable, non-redundant format.

However, what if my array were not [2, 3, 4, 3, 6, 7], but an array of thousands of numbers. Maybe even tens of thousands? Based on my first solution model, I’d have to iterate through endless combinations of numbers, even if my sum was still only 6.

That’s a huge waste of computing energy.

I’m not going to get too deeply into the concept of time complexity here, but I want to find a solution that will scale up better than my initial brute force model, due to requiring fewer computations.

In order to do that, I’m going to use a binary search.

I’m going to write a helper function to perform the binary search itself, then a second function that will utilize it to find the the correct addends for our given sum.

let binarySearch = (array, target, start=0, end=array.length-1) => {}

I’ll pass four parameters into the binarySearch helper function:

• array: This is the same array we’ve been iterating through. However, any array passed into this function will need to be sorted low to high in order for this function to work!
• target: This is the number we’re looking for — when applied in the twoSum solution, this will be the second addend in a pair.
• start: The index at which we start iterating.
• end: The index at which we stop iterating.

First things first, I want to find the middle of the array. If it contains an even number of elements, I’ll need to round down.

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)
}

I’m using the

(start + (end — start)/2)

method to get the midpoint so as to avoid some potential edge case errors as explained here.

I want to round the midpoint down to the nearest integer. I could use

Math.floor(start + (end — start)/2)

to handle my rounding, but the bitwise operator ~~ can do the same job of rounding down to the nearest integer a bit more quickly.

Since I’m going to be testing for several different cases in this function, I’m going to use a switch statement instead of an if/else statement.

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false 
    }
}

As I’m trying to make this approach a bit more efficient, I’m starting with a few cases that have relatively low time complexity cost.

I check for the cases where:

• 1: The first number is the target number.
• 2: The middle number is the target number.
• 3: The last number is the target number.
• 4: The array or array section through which I want to iterate is empty.

If none of these cases are true, I can move on to the iterating.

To do so, I’ll add two more cases:

let binarySearch = (array, target, start=0, end=array.length-1) => {
    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false
        case array[midPoint] > target:
            return binarySearch(array, target, start+1, midPoint-1)
        case array[midPoint] < target:
            return binarySearch(array, target, midPoint+1, end-1)    
    }
}

If the middle number is bigger than the target, I know that our target number is somewhere between array[start] and array[midpoint]. Therefore, I recursively call our binarySearch function on a new set of numbers, which will be only the elements between array[start] and array[midpoint].

Additionally, as we’ve already checked array[start] and array[midpoint] against to see if either matches our target number in our initial cases, we can exclude those from our list, leaving only the elements between array[start+1] and array[midpoint-1].

This will find a new start, end, and midpoint, and repeat the function on the now-halved collection of elements.

The last case is for if the middle number is smaller than the target number. In this case, we recursively call binarySearch on the collection of elements between array[midpoint+1] and array[end-1].

The logic to this is similar to the previous case — if the target number is greater than the midpoint in a sorted array, we can be confident that it won’t be in the first half, and can skip iterating through those, only looking in the second half of the array (minus the midpoint and end, which we’ve already checked for a match).

Using this recursive approach, we can find the desired number in an array by repeatedly halving the array, thus performing significantly fewer calculations than we would were we to iterate through an entire array every time we wanted to see if it contained a single element.

let binarySearch = (array, target, start=0, end=array.length-1) => {

    let midPoint = ~~(start + (end - start)/2)

    switch(true){
        case array[start] === target:
            return array[start]
        case array[midPoint] === target:
            return array[midPoint]
        case array[end] === target:
            return array[end]
        case end - start === 0:
            return false
        case array[midPoint] > target:
            return binarySearch(array, target, start+1, midPoint-1)
        case array[midPoint] < target:
            return binarySearch(array, target, midPoint+1, end-1)    
    }
    return false
}

Finally, I’ve added a return statement which allows this function to return false if the desired value is not present.

If this function works as desired, it will repeat until it either finds and returns the desired element or returns false, if the element is not present in the given array. Thus, the return value of the binarySearch function is either the desired element if it is present or false.

let array = [2, 3, 4, 3, 6, 7]

binarySearch(array, 9)
> false

binarySearch(array, 4)
> 4

Great! Now we have our working helper method 🌟

How do we apply this to our two-sum problem though?

We know that we need to start with a sorted array in order to use a binary search, so we’ll begin by sorting our initial array.

Then, we can set up the same basic structures we used previously, by creating two empty arrays: one for storing nested arrays containing our successful combinations of addends, and another for storing the elements in those combinations on the accessible top layer for later checking.

We’ll want to find all those combinations of elements, store them in our nums array, then return that array at the end, just like last time.

let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    // find our number combos that add up to sum
    // check to see if we've already found them
    // if not, add them to nums

    return nums
}

This time, however, we won’t be creating nested loops to iterate through.

This time, we’re only iterating through our array once.

For each element, the value addend will be assigned to the number that would equal sum minus the element.

So, for a sum of 6 and an element of 2, addend would be the integer 4.

let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    for (let i in sortedArray){
      // if sortedArray includes sum minus sortedArray[i], find it
      // push sortedArray[i] and the found number into nums
      // make sure no redundant numbers are pushed
    }
    return nums
}

That gives us a target integer, which is exactly what our binarySearch function needs.

So this time, we’ll use the binarySearch helper function to do the work for us.

let binarySearchTwoSum = (array, sum) => {
    let sortedArray = array.sort()

    let nums = []
    let prevNums = []

    for (let i in sortedArray){
        let addend = binarySearch(sortedArray, sum-sortedArray[i])
        if (!!addend && !prevNums.includes(array[i]) && !prevNums.includes(addend)){
            nums.push([sortedArray[i], addend])
            prevNums.push(addend)
        }
    }
    return nums
}

This way, instead of nesting iterators, we find what the second number in any given combo would be, then use the more efficient binary search method to see if that number is anywhere in our array.

Just as we did previously, we can use the prevNum array as a vehicle to store and check for previously found solutions, so we aren’t returning redundant combinations.

let array = [2, 3, 4, 3, 6, 7]
let sum = 6

binarySearchTwoSum(array, 6)

0: (2) [2, 4]
1: (2) [3, 3]

Great! This also returns our desired result 🌟

3: HASH

Using a binary search made our last solution more efficient than the brute force nested loops solution, but is it possible to improve even more?

There’s another tool available to help us efficiently check whether or now our desired addend exists in our array: a hash table.

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      // for each array element, find its addend
      // see if addend is in array
      // if so
      // push array element and addend to nums
    }
    return nums
}

This time, we’re starting with an empty object, storageHash, in addition to our empty nums array.

Just as we did previously, we want to iterate through our array, and find the remainder of sum minus each element. Then, we want to see if that remainder exists in array. If it does, we’ll push both the remainder and the element into the nums array, which we’ll eventually return after our loop resolves.

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

       // if addend is in array
            nums.push([addend, array[i]])
        }
    }
    return nums
}

We can find the desired addend by subtracting the current element from sum, but how can we tell if it exists in the area without using another nested loop or our binary search function?

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

       // if addend is in array
            nums.push([addend, array[i]])
        }
          numsObj[array[i]] = i
    }
    return nums
}

Let’s start using storageHash.

With each iteration, we’ll add a new key-value pair to storageHash: a key of array[i] (the element), and a value of i (the index).

let hashTwoSum = (array, sum) => {
    let storageHash = {}
    let nums = []

    for(let i in array){
      let addend = sum - array[i]

        if (addend in storageHash){
            nums.push([addend, array[i]])
        }
        storageHash[array[i]] = i
    }
    return nums
}

Now, when we find a new addend, and want to check and see if it exists in our array, we can look up that key in storageHash. This is a nice operation to do, as it only requires checking a single specific place in memory, and doesn’t require iterating through a collection of connected elements.

If the key exists in storageHash, then we know that number also exists in array.

Thus, we can safely combine the addend we’ve checked against storageHash with our current array element, and add them to our nums array for later return.

Let’s test it out in the browser console:

let array = [2, 3, 4, 3, 6, 7]

hashTwoSum(array, 6)

> 0: (2) [2, 4]
> 1: (2) [3, 3]

Great! That gives returns our desired result. 🌟

Rather than iterating through every possible combination of array elements, or even finding the desired addend for each element and searching the array for it (even with something as relatively efficient as a binary search), we can now look up each potential addend directly using our hash table.

This approach is also nice because it doesn’t require sorting the initial array, or stripping superfluous correct combinations from the final array.

That’s it! Hopefully these solutions help you tackle the challenge of finding the two array elements that add up to a given sum.

If you’d like to read more about a variety of approaches to solving this problem and their respective benefits, I really like this writeup (warning: automatic pdf download!).