Find two numbers in an array that sums up to K
3 ways to find two numbers in an array that sums to some number
Alright, I know you have probably seen this problem elsewhere so many times but if you are reading this article then I am assuming you are preparing for an interview.
This article will talk about 3 ways to find two numbers in an array that sums to some number, k.
Here’s the context of the problem:
Let’s say we have an array [12, 5, 17, 4, 19, 6, -11] and we want to find two numbers that add up to 36, which is k. After searching through the whole array, we realize the two numbers that add up to k would be 17 and 19.
So…how do we solve this problem?
Solution 1: Brute force algorithm (using a double array to solve the problem)
To find two numbers that add to k, for every number i in the array we try to add number j to i and see if that equals k. If it is, return the pair.
Here is an example:
Note that this algorithm is going to require o(n²) for performance and o(1) for space complexity since it requires double looping and we only really store two values for returning. Not necessarily the best solution right?
Solution 2: double-pointer approach
With this approach, the idea is to take a sorted array and use i and j index to find the pair that matches to k.
Here is a catch: the array must be sorted. If it is not sorted then this approach does not work.
If you are preparing for an interview, assume the array is not sorted. Now you have to choose when sorting algorithm to use. If you are using arrays.sort, fine. Understand what sorting algorithm is used behind the scene and understand its space and performance complexity. If not, merge sort and quick sort are common sorting strategies to get the job done.
In fact, I wrote an article about how quicksort works:
Once the array is sorted, you start i at 0 and j at arr.length -1, end of the array. You take the value at each index and sum it up. If the value is greater than k, move j by -1. Because the array is sorted, all the elements that are bigger will be placed to the right, where j will be located. Otherwise, if the value is less than k, increment i by 1.
We repeat this process until i is greater or equal to j, indicating no pair of values match k, or if we find a pairing that sums up to k.
Here is the code:
In this one, the complexity of the algorithm depends on the sorting. If the merge sort is used, it will o(n log n) for performance, o(n) for space. You can look at their sorting algorithm’s space & time complexity for further info.
Solution 3: hashing
With this solution, we store the result of each arr[i] in a hashmap if the value doesn’t already exist. On every iteration, we subtract k with the current arr[i] value and store it into a temp value. If the temp value exists in the hashmap, then we know arr[i], and the temp value sums up to k.
Here is the implementation:
For space complexity, this will be o(n) as there is a possibility of going through every element and adding them all into the map. The performance complexity will be o(n) as we only need to loop through every element once.
That’s it! Feel free to try out this problem yourself and nail the coding interview!
