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.

Solution 1 - Using a HashMap

Time Complexity

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).

Space Complexity

As we are putting each element of the array in a HashMap the space complexity is O(n) as well.

Java Source Code

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[]{};
    }

Solution 2 - Using Array Indexes

Time Complexity

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.

Space 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.

Java Source Code

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[]{};
    }

Conclusion

In three words I can sum up everything I’ve learned about life: it goes on.

Robert Frost