Two Sum : Check if a pair with given sum exists in Array

Problem Statement: Given an array of integers nums[] and an integer target, return indices of the two numbers such that their sum is equal to the target.

Note: Assume that there is exactly one solution, and you are not allowed to use the same element twice. Example: If target is equal to 6 and num[1] = 3, then nums[1] + nums[1] = target is not a solution.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, 
which is the required target, we return 
indexes [0,1]. (0-based indexing)

Example 2:

Input Format: nums = [3,2,4,6], target = 6

Output: [1,2]

Explanation: Because nums[1] + nums[2] == 6, 
which is the required target, we return 
indexes [1,2].

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive Approach (Brute Force)

Intuition: For each element, we try to find an element such that the sum of both elements is equal to the given target.

Approach: We traverse through the array, and for each element x, we try to find another element amongst the remaining elements, such that the sum of both the elements equals the target. 

  • Let, first Element is x. The required second element will be, target – x
  • If we find both the elements, we break the loop and return the indices.

Dry Run: Given array, nums = [2,1,3,4], target = 4

Using the naive approach, we first select one element and then find the second element.

  • For index 0, x= 2
    • Then, we iterate through index 1 to 3 to check if target – x, i.e. 4 – 2 = 2 exists. 2 does not exists from index 1 to 3, we move to next index.
  • For index 1, x=1
    • Then, we iterate through index 2 to 3 to find if target – x, i.e. 4 – 1 = 3 exists. 3 exists at index 2, so we store the indices 1 and 2, break the loop, and return the indices.

Code:

C++ Code

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
   	 for (int j = i + 1; j < nums.size(); ++j) {
   		 if (nums[i] + nums[j] == target) {
   			 res.emplace_back(i);
   			 res.emplace_back(j);
   			 break;
   		 }
   	 }
   	 if (res.size() == 2)
   		 break;
    }
    return res;
} 

Time Complexity: O(N2)

Space Complexity: O(1)

Solution 2: Two-Pointer Approach

Intuition: Think about, what if the array is sorted? If the array is sorted, is it possible to reach a sum by traversing the array from both sides simultaneously?

We sort the array, use two variables, each will start from one end of the array, and traverse in both directions till we get the required sum.

Approach: First we create duplicate array and sort that array. Then we traverse through the array, and for each element x, we try to find another element amongst the remaining elements, such that the sum of both the elements equals the target. 

  • Let, first Element is x.
  • The required second element will be, target – x
  • If we find both the elements, we break the loop and return the indices.

Dry Run: Given array, nums = [2,1,3,4], target = 4

  • First we sort the array. So nums after sorting is [1,2,3,4]
  • We take two pointers, i and j. i points to index 0 and j points to index 3.
  • Now we check if nums[i] + nums[j] == target. In this case, they don’t sum up, and nums[i] + nums[j] > target, so we will reduce j by 1.
  • Now, i = 0, j=2
  • Here, nums[i] + nums[j] == 1 + 3 == 4, which is the required target, so we store both the elements and break the loop.
  • Now, we run another loop to find the indices of the elements in the actual array, i.e [2,1,3,4]
  • Then, return the actual indices, [1,2].

Code:

C++ Code

vector<int> twoSum(vector<int>& nums, int target) {

    	vector<int> res,store;
    	store = nums;

    	sort(store.begin(), store.end());

    	int left=0,right=nums.size()-1;
    	int n1,n2;

    	while(left<right){
        	if(store[left]+store[right]==target){

            	n1 = store[left];
            	n2 = store[right];

            	break;

        	}
        	else if(store[left]+store[right]>target)
            	    right--;
        	else
            	    left++;
    	}

    	for(int i=0;i<nums.size();++i){

        	if(nums[i]==n1)
            	    res.emplace_back(i);
        	else if(nums[i]==n2)
            	    res.emplace_back(i);
    	}

    	    return res;
	}

Time Complexity: O(NlogN)

Space Complexity: O(N)

Solution 3: Hashing (Most efficient)

Approach: We can solve this problem efficiently by using hashing. We’ll use a hash-map to see if there exists a value target – x for each value x. If target – x is found in the map, can return current element x’s index and (target-x)’s index

This can be done in constant time.

Dry Run: Given array, nums = [2,3,1,4], target = 4

  • For index 0, x = 2 and currently map is empty.
    • We try to find if target – x = 4 – 2 = 2 is present in the map or not.
    • For now, 2 does not exists in the map.
    • And we store the index of element 2. i.e., mp[2] = 0,
  • For index 1, x = 3
    • We try to find if target – x = 4  – 3 = 1 is present in the map or not.
    • For now, 1 does not exists in the map.
    • And we store the index of element 3. i.e., mp[3] = 1,
  • For index 2, x = 1 
    • We try to find if target – i = 4  – 1 = 3 is present in the map or not. 3 exits in the map, so we store index 2 and value stored for key 3 in the map, and break the loop. And return [1,2].

Code:

C++ Code

vector<int> twoSum(vector<int>& nums, int target) {

    vector<int> res;
    unordered_map<int, int> mp;

    for (int i = 0; i < nums.size(); ++i) {

   	 if (mp.find(target - nums[i]) != mp.end()) {

   		 res.emplace_back(i);
   		 res.emplace_back(mp[target - nums[i]]);
   		 return res;
   	 }

   	 mp[nums[i]] = i;
    }

    return res;
}

Time Complexity: O(N)

Space Complexity: O(N)

Special thanks to Pranendu Bikash Pradhan for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article.