This is the first problem listed on most coding platforms. Here’s the problem statement:
Given an array of unique integers, find a pair of distinct integers (in any order) that add up to a given target sum.
For example:
The array: 4, 19, 8, 6, -1, 15, 10
Target sum: 9
Output: -1, 10
Let’s dive into the solution: There are several ways to solve this, let’s briefly look at all of them and then code the seemingly best one:
Approach 1:
Sum up every pair of integers in the array and select the one that adds up to the target sum. Let’s look at how to do this:
To generate all pairs, let’s run a doubly nested loop over the array and try to pair each integer with every other integer. But, we have to be careful so as to not doubly-generate the pairs. (Meaning: (4, 19) and (19, 4) are the same pair and so should be generated only once.) To do so, while looping over the integers, we should try to pair every integer with only the integers that lie after it in the array.
Time complexity: Since this algorithm uses a doubly nested loop, so time complexity is O(n2)
Space complexity: O(1)
Approach 2:
Let’s see if we can do better than O(n2):
How about we sort the integers in ascending order and then try to pair them up in the following manner:
- set i = 0;
and j = the last index - sum up the array values at indices i, j
(a) if this sum = target sum, then we’re done!
(b) else if this sum > target sum => we need smaller numbers in the pair: so decrease j (since the array is sorted in the ascending order)
(c) else if this sum < target sum => we need bigger numbers in the pair: so increase i (since the array is sorted in the ascending order) - Repeat the above step as long as i<j
If you’re wondering why only so long as i<j: it is because, if it weren’t so i.e. if we had a condition like while(i<array.length && j>=0) then, since we either we do i++ or j– at a time, then at one point, we’ll have i=j and that is a sum we do not want to consider as we want sum of 2 distinct integers. Besides, after i and j cross each other, there can be no two elements in array with i on the rhs and j on the lhs that can add up to the target sum because if there were, then the pair would already have gotten discovered with i on the lhs and j on the rhs much earlier in the algorithm.
It is interesting to note that if the given sum is < the least sum possible in the array, then j will keep getting decreased and will eventually reach i at the left-most end of the array and then the condition i<j will become false and we can return a code for pair not found. Whereas, if the given sum is > the greatest sum possible in the array, then i will keep getting increased and will eventually reach j at the right-most side of the array and then the condition i<j will become false and we can return a code for pair not found. And, in case the given sum neither < the least sum possible nor > the greatest sum possible in the array i.e. it is somewhere in between, yet, not in the array then eventually, after a series of i++, j– in some order, the condition i<j will become false and we can return a code for pair not found.
Time Complexity: 1. Sorting at avg: O(n.logn) 2. Looping over integers with pointers i, j: O(n). Therefore overall avg. time complexity is O(n.logn)
Space complexity (other than the space needed for sorting (if any)): O(1)
Approach 3:
Now, let’s try to do better than O(n.logn) by using some additional space.
This time we’ll maintain a set to store the integers in the array that we’ve already visited.
Loop over the array and at every integer, check if there’s any integer in the set, which when paired up with the current integer gives us the target sum, if so: we’re done, else, we’ll add the current integer to the set (i.e. mark it visited) and move on to the next integer.
Time Complexity: O(n) to loop over all integers in the array
Space Complexity: O(n) (to store the elements in the set)
Here’s the solution for this approach coded in Java:
public int[] pairSum(int[] array, int target) {
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<array.length;i++) {
if(set.contains(target - array[i])) {
return new int[]{array[i], target - array[i]};
}
set.add(array[i]);//mark array[i] visited
}
return new int[0];//represents that the pair was not found
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! 🙂 Happy New Year!
The Code Scribbbler 