Two Number Sum — Part I
This marks the beginning of Sooinc’s and my pair programming journey to solve this problem from AlgoExpert. Suppose we have a function that takes in an array of distinct integers and an integer that represents the target sum. How do we find any two integers in the input array that will sum up to the target sum and return them in an array?
There are a few things to note.
- If no two integers sum up to the target sum, the function should return an empty array.
- There will be at most one pair of integers summing up to the target sum.
For example, if we are given inputs such as
array = [2,4,-5,10,8,1,-6,3]targetSum = 9
We would expect our sample output to be [8,1].
Solution
Since it is an array and we know we will have to somehow go through each pair of elements and compare it to the target sum, our first approach, a brute force solution, would be to utilize a nested for loop. In the outer loop, we will traverse the entire array from the ith index and in the inner loop, we will begin traversing from (i + 1)th index. This will allow us to check every combination of each element in the array. If at any given point, we come across two elements that add up to the target sum, we will push both elements to our result array and return it.
Our first brute force solution is as follows:
Since this solution utilizes a nested for loop, its time complexity will be O(n²). Its space complexity will be O(1).
Now, you might say, why do we need a nested for loop when we are going through the same array? What if we could have pointers that we can move along the array if a certain condition is fulfilled? What if we could sort the array to make our search more efficient?
This leads us to our next solution, where we begin by sorting the array in an ascending order. We then proceed to placing left and right pointers to both ends of the array, specifically the first and last index of the array. Then, we would check the current sum of both elements targeted by the pointers and compare it to the target sum. If it is equal to the target sum, we can simply return both numbers in an array and we’re done! If the current sum is larger than the target sum, we know we would have to decrease the value of the current sum. In order to do that, we would have to decrement the right pointer by 1 so that it will now target an element with a lower value. If the current sum is smaller than the target sum, we will have to do the opposite by incrementing the left pointer by 1 so that it will now target an element with a larger value. When both our right and left pointers converge, we know we have searched the entire array and can return an empty array if no sum of both elements add up to the target sum.
Here is a snapshot of our optimized solution:
In contrast to our brute force solution, we are only looping through the entire array once. We might think this has a big O of n time. However, since we are sorting the array and we know that the worst case scenario for a Quick Sort is O(log(n)). So this leaves us with a time complexity of O(nlog(n)). Our space complexity stays the same, at O(1), as we are traversing through the same array.
While these are interesting ways to solve the same problem, click here to see how we approached this problem in a different angle.
