Two Number Sum DS&A

I started learning DS&A a week before my mock interview. Two number sum is the first coding challenge question I ever solved. For the mock interview it was the question I was asked. I was excited. I thought I did it, I know exactly what to code for the solution. Before I go further in saying what my solution was. I’ll explain the problem.

Problem:

You have an array of numbers and a target sum. Find the pair of numbers that equal the target sum. My mock interviewer asked it this way.(At least this is the way I remember it) “Let’s say you have a list of movie times and you are going to take a flight. But you need to know what two movies you can watch to equal the length of flight. For example your flight is 4 hours long. You can watch two movies that are 2 hours long.” With this explanation I knew fairly quickly we were talking about the two number sum.

input: [40, 64, 33, 5, 22, 10] target sum: 38

output: [33, 5]

• ** note: You can be asked for different types of outputs. For ex: Boolean or Indexes.**

My Solution:

function twoNumberSum(array, targetSum) {
 for(let i = 0; i < array.length; i++) {
      const numberOne = array[i]
          for(let j = i + 1; j < array.length; j++) {
             const numberTwo = array[j]
             if(numberOne + numberTwo === targetSum) {
               return [numberOne, numberTwo]
              }
         }
    }
      return []
}

While in my mock interview I made sure to voice my process and how I came to the solution. I pseudocode the steps I wanted to take. And then I proceeded to code the solution. I finished in record time. ( I thought to myself “What will happen now? Will the interview end sooner than scheduled? I can take a breath now I solved it. There’s nothing else for me to do”) But I soon learned that was not the case. I did solve it and I did get the correct answer, but….

He said: “Okay thats good, now what Big O notation is this? … and How can you make it better?”

When I say I was shooketh! I mean I completely shut down. My brain said “NOPE SORRY CAN’T HELP YOU”

With this being new to me I definitely was not a genius at DS&A’s. I learned a lot from this mock interview. I really am glad I went through it to get a taste of what’s to come. I studied up on Big O notation and realized that this problem could be better. I definitely did not have the fastest solution.

After the mock interview I made sure that I understood how to improve my code and why it was better. Below is the linear solution.

function twoNumberSum(array, targetSum) {
  const nums = {}
 for (const number of array) {
  const match = targetSum - number
  if(match in nums) {
   return [match, number]
  } else {
   nums[number] = true
  }
 }
 return []
}

For the original solution it was O(n²) but with the second solution it has improved to O(n)(linear solution).

The reason first solution came out to be O(n²) is because I was using a nested loop. Removing that option and using an object I am able to have a better, faster and space saving solution.