Two Sum - Challenge 4

This forms up part of the building blocks in most algorithms challenges involving arrays manipulations.

Intro
This challenge involves taking two parameters, an array, and a number. The goal of this challenge is to return a pair of sub-arrays, each pair adding up to the number given. For example, if we pass [1,6,4,5,3,3] and 7 as our arguments, we should get [[6,1], [3,4], [3,4]] as our result.

Guidelines

1. Result should be an array of arrays.
2. Any number in the 'numArray' can be used in multiple pairs.

There are many ways of accomplishing this:

1. It can be done in 0(n^2) time complexity. This involves nested loops.
2. It can also be done in 0(n) time complexity as we know more performing. This utilizes a hash table. We are going to utilize this.

Let's Dive right in

As usual we will define a function twoSum that takes in two parameters numArray and sum.

function twoSum(numArray, sum){

}

Next, we will define a variable, pairs which will store our result of nested pairs of numbers from the numArray that adds up to our sum

function twoSum(numArray, sum){
   let pais = [];

}

Next, we want to loop through our numArray and gain access to every number.

function twoSum(numArray, sum){
   let pais = [];

   for(let i = 0; i < numArray.length; i++){

   }
}

We, will define the current number that we are on by:

function twoSum(numArray, sum){
   let pais = [];

   for(let i = 0; i < numArray.length; i++){
      let currNum = numArray[i]
   }
}

Now, this is where the main functionality of our function takes place. We want to use a hash table and push every number that we iterate through into that hash table. In this algorithm, we will use an array as a hash table, but you can use an object. They both achieve the same functionality.

So on every iteration, we want to check this hash table to see if the current's number counterpart is present in that table. For example, if our current number is 4, the number we are looking, to sum up to is 7. The counterpart of 4 would be 3 because 4 + 3 = 7. So we want to check our has table to check if our counterpart (3) already exists in the hash table. If the counterpart doesn't exist in the hash table, we already know that we have already iterated through that number in our array, we can, therefore, take these two numbers as a pair and push them into our pairs array. Basically that's all we have to do. So let's proceed and write:

function twoSum(numArray, sum){
   let pairs = [];
   let hashtable = [];

   for(let i = 0; i < numArray.length; i++){
      let currNum = numArray[i]
      let counterPart = sum - currNum
      if(hashTable.indexOf(counterPart) !== -1){
         pairs.push([ currNum, counterpart])
      }
      hashTable.push(currNum)
   }
   return pairs
}

And, that's it!

See you in the next one!

Happy Hacking!