AlgorithmsData StructuresContact
Two Number Sum
Rami Del Toro
Rami Del Toro
August 20, 2021
10 min

Table Of Contents

01
Solution 1 - Using a HashMap
02
Time Complexity
03
Space Complexity
04
Java Source Code
05
Solution 2 - Using Array Indexes
06
Time Complexity
07
Space Complexity
08
Java Source Code
09
Conclusion
Two Number Sum

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

Two Number Sum With Hashmap Flowchart
Two Number Sum With Hashmap Flowchart

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

two number sum algorithm with array indexes flow diagram
two number sum algorithm with array indexes flow diagram

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

Tags

algorithmsarrayeasy

Related Posts

How to implement the MergeSort Algorithm
How to implement the MergeSort Algorithm
October 10, 2021
25 min
© 2022 Rami Del Toro ,All Rights Reserved.