Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
The algorithm traverses through the array once and does a calculation to check if it found the target numbers, there for the time complexity is O(n).
As we are putting each element of the array in a HashMap the space complexity is O(n) as well.
public int[] findWithHashMap(final int[] array, final int targetSum) { final var numbersMap = new HashMap<>(); for(var number : array) { final var diff = targetSum - number; if(numbersMap.containsKey(diff)) { return new int[]{diff,number}; } else { numbersMap.put(number,null); } } return new int[]{}; }
We traverse the array once, while utilizing the lest and right index, that would be O(n). However, for this algorithm to work we need to sort the array first. A good search algorithm like QuickSort or MergeSort would be O(nlogn). As a result, O(nlogn) would be the time complexity.
Since this solution does not need to add any extra space, the space complexity is O(1). It is always great to implement a solution with O(1), does not get any better than that.
public int[] sortAndFind(int[] array, int targetSum) { Arrays.sort(array); var leftPointer = 0; var rightPointer = array.length -1; while(leftPointer < rightPointer) { var currentSum = array[leftPointer] + array[rightPointer]; if(currentSum == targetSum) { return new int[]{array[leftPointer],array[rightPointer]}; } else if (currentSum < targetSum) { leftPointer++; } else { rightPointer--; } } return new int[]{}; }
In three words I can sum up everything I’ve learned about life: it goes on.
Robert Frost