Data Structures & Algorithms in Java – Arrays – Two sum

Problem:

Given an array of integers and a sum , find two numbers in the array which match that sum and return their indices.

Example:

Input:

[2, 6, 3, 9] – array of integers

8 – sum

Output:

2 + 6 = 8 ,

index of 2 is 0

index of 6 is 1

So answer is [0,1]

Try it out here:

https://leetcode.com/problems/two-sum/

Solution:

The easiest solution for this problem is to traverse each element in the list and check if on adding any of the remaining elements in the list to the original element matches the sum.

This requires two for loops. For each element in the list you check each other element in the list.

The time complexity is O(n2).

One solution to this of time complexity O(n) can be obtained using the following hints.

Hint:

1. You need to make use of the difference between the target and each element in the list.
2. You need to use a secondary storage – a HashMap

The algorithm is:

STEP1: Store the indexes of each element in a hashmap

STEP2: Iterate through each element in the list

STEP3: For each element, find the difference of it with the sum

STEP4: Find the index of this difference value in the hashmap

STEP5: If this difference plus the original element equals the sum , return the two indices (the original element’s index and the difference value’s index from the hashmap). During this step make sure the index of the difference is not equal to the current index (don’t add an element to itself)

Code:

Here is the code in Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
   
        
        
        var indicesMap = new HashMap<Integer,Integer>();
        
        
        for(int i=0;i<nums.length;i++){
            
            
            indicesMap.put(nums[i],i);
        }
        
        
        for(int i=0;i<nums.length;i++){
            
            
            var difference = target - nums[i];
            
            var differenceIndex = indicesMap.get(difference);
            
            if(indicesMap.containsKey(difference) && i !=differenceIndex ){
                
                
                return new int[]{i,differenceIndex};
            }
        }
        
        return new int[]{};
    }
}

Boundary Conditions:

The above code does not check boundary conditions.

What if the input array of numbers is empty?

Add a check for the same.

That’s it!