Solving a Classic — Two Num Sum
Almost all devs have seen or heard of this classic problem before.
“Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any of the two numbers in the array add up to the target sum, they should be returned in an array. If no two numbers add up to the target sum, return an empty array.”
First things first, I like to check what the question is asking to be returned in the end, in this question it is either asking for an array with two nums that add up to the target sum or an empty array, so we know we have to instantiate an empty array at some point. Why not start at the beginning.
Here we create an array to store our results and we return it at the end and with these two small lines of code, we will actually pass some test cases, that is, ones that don’t have any nums that add up to the target sum and are expecting the return of an empty array. After we instantiate a results array, we’re gonna get down to brass tax and loop through our input array two times. We use a nested loop here to compare each number in our array to another, so we start at the very beginning with the first two numbers and if they don’t add up to the target sum, we increment the number on the second loop until we reach the end at which point, we will continue along and return the array with or without two numbers depending on whether or not it has met a condition.
Ah, now look at that, a beautiful and simple solution that should be easy to understand. Lets go over what we did one more time. We instantiate our result variable in this case it holds an empty array for us. Then, we loop through the input array two times to compare one number to another and see if they both add up to the input, target sum. If both numbers meet this condition, we add them to our result array. In the end we return our result array and it will either be empty if the condition we just talked about was not met or it will contain two numbers from the input array that add up to the input target sum. This problem may seem simple but its an important one for understanding how to deal with more complex problems. There are more elegant ways to solve this problem as well but this is the simplest but its downside is its time complexity, which comes out to be Big O(n²). We can cover solving this problem in a more efficient way in a future article. For now, Happy Coding!