Two Sum

Parents : Leetcode

Siblings :

Date and time note was created	$= dv.current().file.ctime
Date and time note was modified	$= dv.current().file.mtime

Question Link : 1. Two Sum

Question Breakdown

• Take two numbers a + b = t
• where a,b : numbers whose index to be found and t: target sum
• only one solution exists in this problem (multiple might exist )
• the same element must not be repeated for usage.

Approaches

Brute Force

Algorithm

I can traverse through the array through two loops and check for each number to be the sum or not.

Code

for(int i=0;i<n;i++){
	for(int j=1;j<n;j++){
		if(i==j)
		continue; 
		else if (A[i]+A[j]==target){
		 return {i,j};
		}
	}
}
return {};

Time Complexity

$O(n^2)$ As two nested loops are used which are dependent on each other.

Space Complexity

$O(1)$ No extra(auxillary space) is required.

Optimised One(Time optimisation but two passes )

Algorithm

• We can use Hashmap for storing the index-value pair for fast searching of the element.
• This approach solves the problem in two passes
  • one pass to make the hashmap
  • another pass to fetch the value from it.

Code

// Function to find the second index 
int findSecondIndex(int target ,int firstIndex,int  firstValue,unordered_map<int,int>mp){
        int secondValue=target-firstValue;
        for(auto&it:mp){
           if(it.second==secondValue)                                        
           {    
               if(it.first==firstIndex)
                continue;
               else {
                   return it.first;
               }
           }
       
        }
         return -1;
    }
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;// to store index-value pair
        for(int i=0;i<nums.size();i++)
            mp[i]=nums[i];
        for(auto&it:mp){
            int secondIndex=findSecondIndex(target,it.first,it.second,mp);
            if(secondIndex!=-1){
                return {it.first,secondIndex};
            }
        }
        return {};
    }
 

Time Complexity

$O(2\ast N)$ For the insertion and retrieval in hashmap in two passes.

Space Complexity

$O(N)$ For the hashmap used.

Optimised Two (Time optimisation but single pass)

Algorithm

• We can use Hashmap for storing the index-value pair for fast searching of the element.
• This approach solves the problem in one pass as we first check the difference and then insert the element into the hashmap i.e For example we need to insert 2 in the hashmap and target sum = 9 we would first check if the complement=9-2=7 exists in the hash map and if so return the index immediately otherwise insert and check for the next element.
• decrease to one pass as checking and afterwards inserting in the hashmap is done in one go.

Code

 vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;// to store index-value pair
        for(int i=0;i<nums.size();i++)
        {   if(mp.find(target-nums[i])!=mp.end()){
                return {mp[target-nums[i]],i}; 
            // first we check the difference of target-current element for existence and then we put the element in the hash map doing so reduces the load of re-checking again (#incomplete: perform the main task before the task of insertion)     
            } 
            mp[nums[i]]=i;// insert the element
        }
        return {};
    }

Time Complexity

$O(N)$ Single pass

Space Complexity

$O(N)$ Hashmap is used.

References

Footnotes