How to Solve the Dreaded twoSum Algorithm WITHOUT Nested For Loops!

TL;DR

If you're looking for a quick solution on how this works, let me give you the gist of this absolute novel I've written on this topic. However, if you wish to dive super deep into the reasoning of how this works, I invite you to read the entire article. Here's the short and sweet of it:

 const twoSum = (array, sum) => {
   //declare a variable, 'numObj', and assign it to an empty object
   const numObj = {};

   //iterate over 'array' using a for...in loop
   for (const index in array) {

    //declare a variable, 'targetSum', that will be assigned 
     //to the difference between 'sum' and the current element
     let targetSum = sum - array[index];

    //check to see if 'numObj' contains 'targetSum'; 
     //if it does, return true
     if (numObj[targetSum]) return true;

    //otherwise, populate 'numObj' with the current element 
     //as the key and it's index as the value 
     numObj[array[index]] = index
   }
  //if no matches are discovered, return false
   return false
}

Basically all this is doing is creating an object to store all of the elements from array into, with the key being the actual element value and the property's value being the index of the element.

We determine targetSum as the other value we need to sum with the current element to equal the value of sum. If our object doesn't contain that targetSum key, we cache that current element into numObj and continue on until we find an element that can be summed with targetSum to produce a true return. Othwerwise, we just return false.

If that doesn't make any sense at all, please keep reading! <3

As of recently, I discovered that within most technical interview settings, there exists an algorithm challenge 'twoSum' that is quite prevalent for those who have had the unfortunate experience of being on the scrutinizing end of said interview (luckily for me, I'm still at the script kiddie portion of my journey and haven't gone through one yet).

Regardless, as I started to work my way through this challenge and discovered the multitude of ways to solve this problem, I realized that the "brute-force" method of using nested for-loops isn't exactly ideal when you have thousands, or even hundreds of thousands of elements to deal with!

Let's take a look at the brute-force method of using nested for-loops, just for posterity's sake:

Brute Force Method

const bruteForceTwoSum = (arr, targetSum) => {

//declare an array to hold target elements subarray
    const targetElements = [];

//iterate over 'arr' on the current element
  for (let i = 0; i < arr.length; i++) {

//iterate over 'arr' on the current + 1 element
    for (let j = i + 1; j < arr.length; j++) {

//if the sum of the outer and inner element is equal
 //to 'targetSum', push those elements to 'targetElements'
    if (arr[i] + arr[j] === targetSum) {
    targetElements.push([arr[i], arr[j]])
      }
    }
//return the entire array of subarrays when finished iterating
  } return targetElements
}

const myArr = [1, 2, 3, 4, 5, 6];

//should return [ [1, 4], [2, 3] ]
console.log(bruteForceTwoSum(myArr, 5))

While this method is appealing, easy to reason about and doesn't take much of a concerted effort to commit to memory after you spend some time on it, the time/space complexity gets pretty unruly once you have substantial datasets to manipulate. Not that I know anything about that, but that's what I hear everyone else say, so 🤷‍♂️

After I began researching other ways to solve this, sans the nested for-loop method, I quickly discovered that a lot of people have strong ideas on how to do this; implementations of the Map() object, use of the double bitwise NOT operator (~~), and so on and so forth, I thought there has to be a better way for a n00b such as myself to comprehend! And I did find it!

Enter Object Implementation

So let me just say that this took quite a bit of mental strain for me to comprehend, so don't feel discouraged at all if that same thing happens to you. That just means you're actively processing new, foreign information and that is a net-gain in the overall spectrum of things!

I'm going to do my best to clarify the pain-points I encountered when deciphering all of this, so that you'll hopefully come away from this article in having a good understanding of the basics of this approach. Let's dive into it!

 const twoSum = (array, sum) => {
   //declare a variable, 'numObj', and assign it to an empty object
   const numObj = {};

   //iterate over 'array' using a for...in loop
   for (const index in array) {

    //declare a variable, 'targetSum', that will be assigned 
     //to the difference between 'sum' and the current element
     let targetSum = sum - array[index];

    //check to see if 'numObj' contains 'targetSum'; 
     //if it does, return true
     if (numObj[targetSum]) return true;

    //otherwise, populate 'numObj' with the current element 
     //as the key and it's index as the value 
     numObj[array[index]] = index
   }
  //if no matches are discovered, return false
   return false
  }

Let's work through exactly what is happening with this code, as it was pretty difficult for me to comprehend the first time I saw it.

So we have a pretty basic setup; we're declaring a function twoSum that has two parameters: an array and the sum that we want to look for in our pairs of elements

 const twoSum = (array, sum) => {
   //declare a variable, 'numObj', and assign it to an empty object
   const numObj = {};

Once we enter our function, we're then declaring a variable, numObj and assigning it to an empty object. Here's where things get interesting!

The reason why we want to declare an object is so we can store all elements in our array, array, inside of 'numObj'. We store each property in numObj with the current element as the key and the current element's index as the value! This will make it easy for us to determine both the element's value, as well as the element's index, if any tricky interviewer asks for it 💅

Let's move on to the next chunk of code:

 const twoSum = (array, sum) => {
   //declare a variable, 'numObj', and assign it to an empty object
   const numObj = {};

   //iterate over 'array' using a for...in loop
   for (const index in array) {

    //declare a variable, 'targetSum', that will be assigned 
     //to the difference between 'sum' and the current element
     let targetSum = sum - array[index];

One thing that threw me for a LOOP (get it?) when I first saw this implementation is the use of a for...in loop when iterating over an array.

I thought that broke every law in the programmer's handbook, was anathema to what we all are striving for and whoever wrote this was going to be confined to the deepest layer of programmatic hell, as you only used for...in loops with objects right??

Wrong.

For reasons I won't go into right now, this specific problem is much better handled using a for...in loop. Just know that for now, for (const index in array) does exactly what it says it will do; it's gonna loop over our array, where index will be the current element's index value and array is going to be the array we're iterating

let targetSum = sum - array[index] is going to determine what other number in array is going to satisfy the condition of being equal to sum, when added to the current element, which is array[index] in this case.

Basically, this line of code is saying "For this current element (array[index]) we need to find another number (targetSum) that when added together (array[index] + targetSum) will produce the same value as sum.

    if (numObj[targetSum]) return true;
    //otherwise, populate 'numObj' with the current element 
    //as the key and it's index as the value 
     numObj[array[index]] = index

For this section, we're checking numObj to see if we've cached any elements from array into numObj, HOWEVER:

Notice that we're checking numObj for targetSum. Basically what this means is that for the current element, do we have any keys in numObj, when added to the current element, will produce a sum that is equal to sum?

If it does, we're going to return true. Otherwise, we want to cache that current element into numObj, so we can reference later when checking other elements in array.

And finally...

  //if no matches are discovered, return false
   return false

We want to return false if no elements, when added together, equal the value of sum.

Let's see this with some actual data and see what we get:

 const twoSum = (array, sum) => {
   const numObj = {};

   for (const index in array) {
     let targetSum = sum - array[index];

     if (numObj[targetSum]) return true;

     numObj[array[index]] = index
   }
   return false
  }

const myArr = [1, 2, 3, 4, 5]

console.log(twoSum(myArr, 6)) //should return true, as [1, 5] 
                              //is equal to 'sum', which is 6

But what if we wanted to see all possible element combinations in the array that sum up to the value of sum? Objects to the rescue once again! All we do is declare yet another object to hold properties where the key is the first element and the value is the second element that sum up to the value of sum:

const twoSum = (array, sum) => {
    const numObject = {}
    const finalObj = {};

    for (const index in array) {
    let targetSum = sum - array[index]   

     if (targetSum in numObject) {
        finalObj[targetSum] = array[index]      
        }
        numObject[array[index]] = index
      }
      //check 'finalObj' to see if we've retrieved any pairs
       //whose sum equals 'sum'
      if (Object.entries(finalObj).length !== 0) return finalObj;

      else return 'no pairs found';
   }

const myArr = [1, 2, 3, 4, 5]

console.log(twoSum(myArr, 6)) //should return {1:5, 2:4}

If you've made it this far, wHAT are you doing with your life?? Don't you have one?? :P I am absolutely joking and I thank you very much for your time.

Hopefully this helped to clear up some understanding on how all of this works! If for nothing else, it helped me to solidify this in my brain by spending literal hours on typing this out.

Cheers! <3