How to Solve the Dreaded twoSum Algorithm WITHOUT Nested For Loops!
Tags: twosum, javascript, interview, algorithms
Published: 2023-07-16 23:15:03

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