Solving the two number sum problem efficiently

In the journey of a software engineer, solving algorithm questions comes up now and again, we like to solve it for various reasons, ranging from improving on our ability to think and solve a problem efficiently to preparing for a technical interview amongst many other reasons.

image-credit — http://clipart-library.com/

That being said, the Two Number Sum problem is a very common algorithm question that everyone will come across at some point… I decided to solve it in two ways using Javascript and found out which method is more efficient, but first, the question:

Solution 1:

https://gist.github.com/d-beloved/77f02f17e74440edbe71592b57330585#file-numsumalgo-js

Explanation: The method used above is basic algebra, the question says to find two numbers in the array which when added together will be equal to the target value also supplied. So, using the rule of simple subtraction, we have the target value, let’s call that targetSum , a hashTable (an object) is initialized, then a for of loop is initiated to traverse through the given array once, for every value picked, the second value is calculated by subtracting the current value from the target sum, then the hashTableis checked to see if it contains a key == second value, if it is not, the current value is added to the hashTable, and if it is, the second value and the current value is returned as the result.

Using a simple example, I explain.

givenArray = [1, 4, 7, 5, 2, 6]
targetSum = 10

So, at the run of the first value in the array where value = 1, we get the following

hashTable = {}
yValue = 10 - 1
yValue = 9

Since 9 is not yet in the still empty hashTable, the value 1is added in there. This continues as the loop runs until eventually, we get to where value = 6

hashTable = {1:true, 4:true, 7:true, 5:true, 2:true}
yValue = 10 - 6
yValue = 4

Checking if the hashTable contains the second value gotten, it is there! therefore, we return the result, [4, 6] , and yea, that’s all 🕺 .

Solution 2:

https://gist.github.com/d-beloved/77f02f17e74440edbe71592b57330585#file-numsumalgo2-js

Explanation: Using the sorting method, this is pretty much very interesting and it gets the work done in less than half the time of the last solution. Here’s how it works; given a simple array and the target sum

givenArray = [1, 4, 7, 5, 2, 6]
targetSum = 10

The array is sorted and we have this:

sortedArray = [1, 2, 4, 5, 6, 7]

A loop is initiated, picking the first value and the last value in the sorted array, we add it together 1 + 7 = 8 , then we check the result with the value of the targetSum , if the value is less than the targetSum , as it is in this case, the first pointer is moved to the second value in the sortedArray and the loop is run again => 2 + 7 = 9 , the check is done again and it is determined to be smaller than the targetSum , so the first pointeris moved again and the loop continues, we have this => 4 + 7 = 11 , the check is done and we can see that the targetSum is less than the new value gotten, now the second pointer is moved, (note that if the first pointer is shifted instead, the value will continue to be larger than our target sum). By moving the second pointer and the loop runs, we get => 4 + 6 = 10 , which happens to be equal to our target sum, hence we return the result [4, 6] 🎉

Conclusion: The two methods above do not exhaust the methods of solving this algorithm question, but it does the work of solving the question well enough. The first solution solves the question with a time and space complexity of O(N). While the second solution solves the question with time complexity of O(nLog(n)) while the space complexity is O(1) (constant time).

The code is available on my Github gist.

Give some claps 👏 if this helped 😃 😊.