The Code Talks - Code - 2 Sum

Code - 2 Sum | Two Sum Problem

2 sum or Two Sum is a quite popular problem which is generally asked by many in interviews or even in coding competitions.

PROBLEM : The Two Sum problem involves finding two numbers or index of two numbers present in an integer array whose sum matches the given target. For example, in a given integer array [4, 6, 10] and target 14, the output or the solution would be 0,2 because we would get the target 14 as the summation of value present at 0^th index of the array and 2^nd index of the array i.e. 4+10 hence 0,2.

SOLUTION: There are different ways or approaches to solve this problem. We would look at what can be called brute force and one which is kind of efficient in terms of time complexity and what many would expect as a solution in competitions or interview.

APPROACH 1 : BRUTE FORCE

In this approach we would normally have to iterate over an given array multiple times. We would start with first element and then tally that with the rest of the elements to whether the sum of those two matches the given target or not. If we do not get a match for the first element we would move over the 2^nd element and continue the same approach.

The JAVA code for the same would look like this.

public static int[] brute(int[] numArr, int target) {
        
        int[] indicesOfTwoNum = new int[2];
        
        for(int index=0; index < numArr.length; index++) {
            
            for(int compIndex=index+1; compIndex< numArr.length; compIndex++) {
                if(numArr[index]+numArr[compIndex]==target) {
                    indicesOfTwoNum[0] = index;
                    indicesOfTwoNum[1] =  compIndex;
                    break;
                }
            }
        }
        
        return indicesOfTwoNum;
}

As you can see and understand from the above code, time complexity for this approach would be O(n²).

APPROACH 2 : COMPLEMENT

While the first approach was a basic one and more of a brute force, this approach would be more like an intuitive approach. As part of solution what we need is

x + y = target

where x, y = the elements in the array at different indices. Now that would also mean that say if we have x as an element,

y = target-x;

So we would have to check if y exists in our array. And if it does exists, we have a match we can return the indices or else move towards the next element. This reduces the time complexity from O(n²) as per the first approach to just O(n).

Let's see how this would look in JAVA.

public static int[] usingComplement(int[] numArr, int target) {
    
        int[] indicesOfTwoNum = new int[2];
        
        //Taking an additional data structure
        List<Integer> dataList = new ArrayList();
        
        for(int index=0; index < numArr.length; index++) {
            //Getting the difference between the target and our value.
            int complement = target - numArr[index];
            
            //Check if the complement is present in the list.
                if(dataList.contains(complement)) {
                    indicesOfTwoNum[0] = index;
                    indicesOfTwoNum[1] =  dataList.indexOf(complement);
                    
                    //Break and stop the processing once we have the match
                    break;
                }
            
            //If not match, then add the number to 
            //the list and move to next element in array. 
            dataList.add(numArr[index]);
        }
        
        return indicesOfTwoNum;
}

And as we said, looking at the code we can see that the time complexity for the same would be O(n).

Now the reason why did we use ArrayList is because it preserves the insertion order. So whenever we would do indexOf a given value then it would return us the same position which reflects the position of the element in the array as well. One can also use HashMap and use key as the element and value as the index of that element in the array.

The second approach is by far efficient as well as easy to navigate and understand once we get the gist of the logic. Well, that's about the 2 Sum problem. There are different variations to this problem as well 3 Sum, 4 Sum and so on.. We will be looking at the same. Until then remember to hear what the code talks!!