The Two Sum problem in Java

Two Sum problem is the most common question one can come across while preparing for job interviews in developer roles. I'm writing this blog to tell you about the various approaches you can follow to solve this problem in Java, ranging from the easiest to the best approach.

The problem

You are given a set of numbers in the form of an array and a target sum. You have to find two numbers in this array such that their sum is equal to the given target value. How would you do so?

Easiest and Naive Approach: Brute Force (as always!)

You iterate over each element of the array(x'th element) and create another loop inside the above loop from (x+1)'th element to the end. In each iteration you check if the sum of current element of outer loop and current element of the inner loop add up to the sum. Easy right? Has the highest complexity though!

Code

Following is the code for this approach:

public static int[] getTargetSumIndices(int[] arr, int target){
        for(int i = 0; i < arr.length; i++){
            int x = arr[i]; // element x
            for(int j=i+1; j < arr.length; j++){
                int y = arr[j]; //element y
                int sum = x + y;
                if(target == sum){
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {-1, -1}; // not found
    }

you can use the indices further in the main method get the actual array elements by calling it like this:

public class Main {
    public static void main(String[] args) {
        int[] arr = {11, 2, 5, 0};
        int target = 17;
        int[] result = getTargetSumIndices(arr, target);
        System.out.println("Result: " + arr[result[0]] + " and " + arr[result[1]]);

    }

    public static int[] getTargetSumIndices(int[] arr, int target){
         ...
    }
}

Issues

This might seem like an easy solution to this problem but it incurs the worst time complexity of O(n2) due to a nested for-loop. The best time complexity scenario would be O(1) which would happen if the first elements of outer and inner loop summed up to be the target. Space complexity would be constant with a O(1).

A better approach: Sort + Binary Search

So as we saw that worst time complexity is too big, we want an approach which can work faster for bigger inputs. In this approach we're going to first sort the array, iterate over each element(lets call it x'th element) of this sorted array, find the complement of x with target sum (sum - x) and apply binary search from the (x+1)'th element to last element to find this complement.
So now, this approach looks like this:

Code

The code for this implementation should look like this:

public static int[] getTargetSumPair(int[] arr, int target){
        // sort the array
        Arrays.sort(arr);

        for(int i = 0; i < arr.length; i++) {
            int x = arr[i]; // element x

            //compute complement of x with target sum
            int complement = target - x;

            //binary search - find index of complement
            int y = binarySearch(complement, arr, i+1, arr.length - 1);

            if( y != -1){
                return new int[]{x, y};
            }
        }
        return new int[] {-1, -1}; // not found
    }

    public static int binarySearch(int num, int[] arr, int l, int h){
        while( l <= h ){
            int mid = (l + h) / 2;
            if( arr[mid] > num ){
                h = mid - 1;
            }else if( arr[mid] < num ){
                l = mid + 1;
            }else{
                return arr[mid];
            }
        }
        return -1;
    }

Issues

This approach is creating a time complexity of O(n*log(n)) which is less than our previous approach, but we can still work on it. The space complexity for this method is O(1). Note that the inbuilt sort method is actually optimized dual-pivot quicksort algorithm which has average case time complexity of O(n*log(n)) on data-type int[], which can convert to O(n²) in worst case.

Let's now look at another interesting approach having the same time complexity.

Another O(n * Log(n)) approach: Sort + Two pointer method

In this approach we have to maintain to pointers initially at the two opposite ends of the given array(which needs to be sorted beforehand). If the sum of the elements at the two pointed locations is equal to the target value then simply return their indices. If the sum is less than the target, move left pointer to right to increase sum value and if the sum is greater than the target, move right pointer to left to decrease the sum's value.
This implementation would visually look something like this:

Code

This is what this approach's code would be like in Java:

public static int[] getTargetSumPair(int[] arr, int target){
        // sort the array
        Arrays.sort(arr);

        // set lower and higher pointers
        int l = 0;
        int h = arr.length - 1;

        // do a while loop until l == h (while l is less than h)
        while(l < h ){
            if (arr[l] + arr[h] > target){
                h--; // as sum is greater than target, make bigger number smaller
            }else if(arr[l] + arr[h] < target){
                l++; // as sum is smaller than target, make smaller number bigger
            }else{
                return new int[] {arr[l], arr[h]}; // this means sum == target, so return the arr elements
            }
        }
        return new int[] {-1, -1}; // not found
    }

Issues

Again, as I said, this is another approach of O(n*log(n)) with space complexity of O(1).

We are now going to look at the hash set approach which significantly reduces the time complexity of this problem.

Hash set

This approach is the best one for the two sum problem as it incurs the least time complexity. So in this approach, we're going to create an empty hashset and iterate over the given array elements one by one. For each array element, we first calculate its complement with the target(target - current element), and then check if this complement exists in the hashset - if no, insert the current element in the hashset and if yes, return the current element and its complement as this would be our answer. This logic would be much clear with the gif given below.

Using a hashset makes this algorithm all the more efficient as hashsets have constant time algorithm or O(1) for insertion and lookup.

Code

The code for this approach is as follows:

public static int[] getTargetSumPair(int[] arr, int target){
        HashSet<Integer> seen = new HashSet<>();
        for( int i = 0; i < arr.length; i++){
            int complement = target - arr[i];
            if(!seen.contains(complement)) {
                seen.add(arr[i]);
            }else{
                return new int[] {arr[i], complement};
            }
        }
        return new int[] {-1, -1};
    }

Complexities

This algorithm would incur a time complexity of O(n) which is for a single for-loop iterating over each array element. Other than that - lookup and insertion operations in Hashset is having complexity of O(1). Note that the space complexity here is O(n) as we're saving the visited elements in the hashset.

Conclusion

Hope you liked reading this blog about the Two Sum problem and various approaches you can follow to achieve the right result for this. This is my first Algorithm related blog on dev.to. Writing blogs has been a really engaging way of learning for me, clarify my doubts and I wish to share my understandings with the community as well so as to clear concepts in a fun way using visual tools like gifs. Following this blog I'll be bringing more such content for the developer community to read and flourish!