Recent Posts

Two Sum Problem

Written by

studymite

Problem:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

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

Output:
[0,1]

Explanation:
nums[0] + nums[1] = 2 + 7 = 9

Understanding the problem

We will be given an array of integers, unsorted i.e. the numbers are inputted in any random manner, and a target value, say x, and we have to return the indices of two numbers whose sum is equal to x.

We will be studying two solutions to this problem:
1. Brute Force Approach
2. Optimized solution (using hashtables)

# Brute Force Approach

The simplest way of solving this problem is two use two for loops. One running from i=0 to the last element, to check for each element of the array and another nested loop from i+1 to the last element to check if the difference of current element and the target value exists in our array or not.

Algorithm:

  1. Initialize i=0 and calculate the difference of target value and number at i and store it in temp.
  2. Initialize j=i+1 and check if the difference exists at this index or not.
  3. If yes return i and j and if not increment j by 1 and check again.
  4. If j reaches the end of array without finding the difference, increment i by 1 and check again.
  5. If i reaches the end of array then no such pair exists.

Code: 

vector < int > twoSum(vector < int > & nums, int target) {
      const int size = nums.size();
      vector < int > answer;
      for (int i = 0; i < size - 1; i++) {
         int temp = target - nums[i];
         // calculating the difference between the current element and target value
         for (int j = i + 1; j < size; j++)
            //searching for the difference in the remaining array
            if (nums[j] == temp) {
               answer.push_back(i);
               answer.push_back(j);
               return answer;
            }
         //if pair found returning it in answer
         return answer;
         //no such pair found, returning an empty array
 }

Time Complexity: O(n2)

# Optimised Approach (Using Hash tables):

In our brute force approach, if we could do the searching part in O(1) time then the time complexity can be reduced to O(n). This is what we will achieve with hashmap. We will make and hash map with index as the element value and it will store the index of that element.

Algorithm:

  1. Initialize an empty hashmap hash.
  2. Initialize i=0 and calculate the difference of target value and number at i and store it in temp.
  3. Check if the number exists in the hash map, if yes return hash[nums[i]] and i.
  4. Else increment i by 1 and check again.

Code:

vector < int > twoSum(vector < int > & nums, int target) {
   //Key is the number and value is its index in the vector.
   unordered_map < int, int > hash;
   vector < int > result;
   for (int i = 0; i < nums.size(); i++) {
      int numberToFind = target - nums[i];

  //if numberToFind is found in map, return them
  if (hash.find(numberToFind) != hash.end()) {
     result.push_back(hash[numberToFind]);
     result.push_back(i);
     return result;
  }

  //number was not found. Put it in the map.
  hash[nums[i]] = i;



}
return result;
}

Time Complexity: O(n)

Two Sum Problem