Solving Two Sum- Two Ways
Hey everyone! In this blog, I wanted to write about the steps to solve a very popular interview algorithm question. The question is called TwoSum on Leetcode and with that let’s begin to code!
The question, as shown above, states given the array, return the two indices such that they add up to the target number. The way I like to solve algorithms is to ask myself what is the question asking? That way, I truly understand what the question is asking. So in this case, example 1 shows us the input which is the given array of numbers, the target number we want, which is 9. And the output which are the indices where the two numbers sum to 9 are located in the array.
In this case, what the example is telling is 2 and 7 are the two numbers in the array that sum to 9. The location of these two numbers in the array is at [0,1].
Let’s say our target number was 13, with the same given array. Do any of those numbers sum to this number? Yes! In fact, 2 and 11 sums to 13, and so the output would be [0,2]. By giving yourself multiple examples you are ensuring you truly understand what is being asked. This is also a helpful trick to try and ask your interviewer a possible example to clarify you are understanding the problem being asked correctly.
A possible edge case for this problem could be; what if there are no two numbers that sum to the target? This is a good question but for time being let’s assume there is always exactly 1 solution and each number can only be used once.
A naive solution to this problem would be to loop through the array, look at each number, and then its counterpart to seewhich adds up to the sum. This can be shown below.
For example, we run through the array looking at each number and 3 to see if it sums to 6. The first one would be: 3 + 4 = 6? It does not, so we move on. The next one would be does 3 + 8 = 6? It does not, so we move on and so forth.
The pseudocode for solving this would be for every num in nums, check every other number and if is === the target, return the indices of those two numbers.
This is the actual code implementation. We have two parameters; nums and target and we will be writing two nested for loops. The first step is to write a normal for loop that is less than the length of the array and increments by 1 or ++. The next step is to create a constant num that pulls out the number we are looking at through direct indexing and save that in a variable; num. We can also save the number we want as a variable, want. This can be achieved by subtracting that number from the target. The next step is to create the inner for loop. We will use the variable j, and start one to the right of i, which is why we used j = i + 1, since we already started at i. Then, we continue the rest of the for loop normally. The next step is to create an if statement to see if nums j is equal to the number we want.
The time complexity of this would be O(n)². This is because we have two nested for loops.
However, because this time complexity is not ideal let’s try and solve it a different way and optimize the code.
Another way to solve this algorithm would be to use the hash table method. The pseudocode looks like this, for every number in nums, calculate the “counterpart”, if it’s in the table return the indices, and if it is not in the table store with an index.
The code using a hashtable would look like this. The first step is, we want to declare the hash table as an empty object. Then, we create a normal for loop, and we will pull out nums[i] to a variable num. We will also set a variable want for the number we want. Then we create an if statement to determine if the number we want is in the hash table. If variable ‘want’ is in the hash table, then let’s pull out the index. To not be confused we can store it in the variable leftIndex. Then we want to return our left index and our right index, or i in that order. If we didn’t find the value we can store the current num in our hash table, with the index as our value.
The time complexity for this solution, since we looped through only once, is O(n) or linear time.
So there you have it. Two ways to solve TwoSum! Of course, there are many ways to solve this problem and so you can try to solve it any way you like.
The inspiration behind this blog was the Interview Espresso course, created by Aaron. I specifically used the TwoSum video explanation. Here is a link to the course which I find super helpful and definitely recommend checking out. https://learn.interviewespresso.com/
Thanks for reading :)
