Two Number Sum (optimized from O(nlogn) to O(N))

One of the most famous interview questions that you can expect to get in your next interview: Two Number Sum, and that given a non-sorted array, find 2 numbers that make a given sum. So, for example given an array: [10, 3, 2 , 9, -1, 8, 13], sum: 7, should give an output of [-1, 8]

One way to solve this problem is to sort the array first and then have a Left and Right pointers and iterate the array in 1 run. The code for this approach is as below:

The above approach will cost us O(n log n) time and O(1) space. That is because of the initial sort that we have done and that is why we have O(n log n) time.

If we try to optimize it then there is a way that we have to give up O(N) space in worst case and that is by using a HashMap and track the numbers while we iterate through the array in one go. The HashMap will obviously be using O(1) time for each check.


So, what do you think ?