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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public static int[] twoSum(int[] array, int sum) { Arrays.sort(array); int l=0; int r=array.length-1; for(int i=0; i<array.length;i++){ if((array[l]+array[r])==Sum){ return new int[]{array[l],array[r]}; }else if((array[l]+array[r])>sum ){ r--; }else if((array[l]+array[r])<sum){ l++; } } return new int[]{}; } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 |
public static int[] twoSum(int[] array, int sum) { int diff; HashMap<Integer, Integer> map = new HashMap<>(); for(int i=0; i<array.length;i++){ diff = sum - array[i]; if(map.containsKey(diff)){ // check if exists return new int[]{array[i], diff}; // if yes then return and save more time possibly O(N-n) } map.put(array[i],i); // add now } return new int[]{}; } |