Two Sum Problem – Leetcode #1

Problem Statement

This problem is from Leetcode – Two Sum Problem. The problem statement is as below:

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

This question is asking us to find two numbers in the given array nums which add up to the given target and return their respective indices. We can safely assume in our design that there is only one solution.

Approach – 1

First lets try the brute force approach.

1. Iterate the given integer array and for each integer iterate the array again in a nested for loop.
2. If two such integers are present which add up to the given target, then store their respective indices and return.
3. As we are iterating in two nested for loops, so the Time complexity of this approach is O(n²).

Lets see the code sample below:

public class TwoSum {
     
    public static void main(String[] args) {
        

		int[] nums =  {3,3,4};
		int target = 6;
		
		TwoSum ts = new TwoSum();
		int[] sol = ts.twoSumFirstApproach(nums, target);

		System.out.println("indices are: " + sol[0] + ", " + sol[1]);

	
    } // end Main 

    public int[] twoSumFirstApproach(int[] nums, int target) {
	        
		 	int[] sol = new int[2];
		 	for(int i=0; i< nums.length; i++) {
		 		
		 		int first = nums[i];
		 		for(int j=i+1; j<nums.length; j++) {
		 			
		 			int second = nums[j];
		 			if(first + second == target) {
		 				
		 				sol[0] = i;
		 				sol[1] = j; 
		 				

		 				return sol;
		 			} //end if
		 		}// end for
		 		
		 	}//end for
		 	

		 	return sol;
	    }

} // end Class

This code returns the following output:

indices are: 0, 1

You can check out the code from Github here: Two Sum Problem – First Approach

Approach – 2

Now lets solve this problem with a HashMap.

1. In the first for loop we iterate through the input integer array and push data into the HashMap such that we have the integer as the key and list of indices where it occurred as the value. Eg: integer 3 in our input occurs ate indices 0 and 1 so its stored in the HashMap as [3, (0,1)].
2. In the second for loop we again iterate through the input integer array. For every integer we calculate the difference from the target value. Then we lookup this difference value in the HashMap. If its present then we return the respective indices.

Lets see the code sample below:

public class TwoSum {

  public static void main(String[] args) {
        

		int[] nums =  {3,3,4};
		int target = 6;
		
		TwoSum ts = new TwoSum();
		int[] sol = ts.twoSumSecondApproach(nums, target);

		System.out.println("indices are: " + sol[0] + ", " + sol[1]);

	
    } // end Main 

   public int[] twoSumSecondApproach(int[] nums, int target) {

		 int[] sol = new int[2];

           // create new Hashset
		 Map<Integer, HashSet> numsMap = new HashMap<Integer, HashSet>();
		 

        /*
	  * Iterate over the input array and populate the HashMap with key as 
      * integer and value as its respective indices it occurred in the input array.
	  * eg: 3 occurs at indices 0 and 1 in the input array, so HashMap should 
      * have entry as [3, (0,1)] 
	  */
		 for(int i=0; i< nums.length-1; i++) {

			 Set<Integer> indexSet = new HashSet<>();
			 indexSet.add(i);
			
			 
			 if(numsMap.containsKey(nums[i])) {
				 
				 Set idxSet =  numsMap.get(nums[i]);
				 idxSet.add(i);
				 numsMap.put( nums[i],  (HashSet) idxSet);
				 
			 }
			 else {
				 numsMap.put( nums[i],  (HashSet) indexSet);
			 }

		 } // end for
		 
	      /*
           * Now iterate the input array again. For every integer check if its 
           * complement i.e. difference from target is present in the map.
           * If its present then return their respective indices
          */	 
		 for(int i=0; i< nums.length; i++) {
			 
			 int rem = target - nums[i];
			 if(numsMap.containsKey(rem)) {
				 
				 if(nums[i] ==  rem && numsMap.get(rem).size()>1 ) {
					 
					sol[0] = (int) numsMap.get(rem).toArray()[0];
					sol[1] = (int) numsMap.get(rem).toArray()[1];
					
				 } // end if

				 else if(nums[i] !=  rem ) {
					 
					 sol[0] = i;
					 sol[1] =  (int) numsMap.get(rem).toArray()[0];
					 
				 } // end if
				 
			 } // end if
			 
		 } // end for
		 
		 return sol;


	 } // end Function

} //end class

This code returns the following output:

indices are: 1, 0

You can checkout the code from Github here: Two Sum Problem – Second Approach

In your opinion what’s the time complexity of the second approach. Please comment below.