Two Number Sum

The perfect solution and in-depth explanation.

ยท

4 min read

The Question

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can't add a single integer to itself in order to obtain the target sum.

Explaining the Problem

The task is to find two unique numbers from an array that would sum up to a particular target value given. These two numbers that sum up to the target value must be different and should be part of the unique numbers in the given array.

Check this example input, given [1,2,3,4,5] as the array and 8 as the target value. Two different numbers from this array should sum up to 8. In this case, the two numbers are 5 and 3, so [5,3] is the expected output.

Solution 1 ( hashMap ) O(1)

function twoNumberSum(array, targetSum) {
  // Write your code here.
  const availableNumbersInArray = {};
    // [1,2,3,4,5] is the array 
    for (let index = 0; index < array.length ; index++) {
      // assume we are at the fourth index
      const currentNum = array[index];  // 5
      const numberToLookFor = targetSum - currentNum; // 3 = 8 -5

      if(numberToLookFor in availableNumbersInArray){ 
// 3 would have been added to the hashmap so the
//  pair 5 and 3 are valid, because both are in 
// the array and sum up to 8
        return [numberToLookFor, currentNum]
      } else {
        availableNumbersInArray[currentNum] = true; 
// assume index 0 to 3 got to this point and were
// added to the hash map making them valid
      }

    }
  return [];
}

Explanation

const availableNumbersInArray = {}

We create a hashmap or object to easily store all available numbers in the array for future reference. We could easily discard this and just make use of the .includes() function. But this is not optimal, unlike searching in a hashmap that is just O(1).

   for (let index = 0; index < array.length ; index++) {

Regular looping using a for loop ( very efficient way to loop anyways)

  const currentNum = array[index];
      const numberToLookFor = targetSum - currentNum;

currentNum is the current number the loop is currently at. Next, let's create a simple logical formula, basic maths. Initially, we are looking for two numbers whose sum would lead to the targetSum. i.e currentNum + y = targetSum , therefore y = targetSum - currentNum. So when we get the value of y , this means that it's a valid pair that when added together with currentNum would give the targetSum.

That answer y is the step one to finding a solution and we could actually just return y and currentNum because they sum up to the target. But the question is this, is the value y in the array given?? That's where the next line of code comes in.

     if(numberToLookFor in availableNumbersInArray){
        return [numberToLookFor, currentNum]

Here, we are checking to see if numberToLookFor is actually a number in the array we are working with. In the simple formula we created above, we want to check if y is in the given array. y would represent numberToLookFor in our case. If we have the number stored yet, then we can return the two numbers. Else, we add the current number to the hash map created, meaning the currentNum is available to be paired with and it's a valid number from the array.


else {
        availableNumbersInArray[currentNum] = true; // number is in array
      }

Like said earlier, we just saying that the currentNum is a valid number from the array. and could be a valid and accurate pair that can be summed up with another number being looped through to get the targetSum.

Again, all we are saying is, " hey! this currentNum is in the array we are working with, so do me a favor and keep this in mind just in case you come across this number and it's the same as the solution to const numberToLookFor = targetSum - currentNum; in a future interation.

Solution 2 ( Array.includes) O(n)

function twoNumberSum(array, targetSum) {
  // Write your code here.
   let pairs = [];

      for (let index = 0; index < array.length; index++) {
          const currentNum = array[index];
          const  pair = targetSum - currentNum; 
          if(array.includes(pair) && pair !== currentNum){
            pairs = [pair, currentNum]
         }
      }
  return pairs;
}

This is similar to solution 1 but we are using the array.includes() method.

Solution 3 ( Two Loops ) O(n^2)

Don't bother about this solution ๐Ÿ˜ช