Two Sum: Array interview question

November 10, 2020   Interview Questions

Problem description

Two sum : Given a vector of numbers vec and an integer target, return the pair of two numbers such that they add up to target value.

Example 1

Input: vec = [1,2,3,4,5,6], target = 8
Output: [2,6]
Explanation : because  2 + 6 = 8, we return [2 , 6]

Example 2

Input: vec = [13,22,14], target = 36
Output: [22,14]
Explanation : because  22 + 14 = 36 , we return [22 , 14]

Constraints

2 <= vec.size <= 10⁵
-10⁹ <= vec.at(i) <= 10⁹
-10⁹ <= target <= 10⁹
time complexity : O(n)

Solution :

we need an effective way to examine if the counterpart exists in the vector. If the counterpart exists, we will return the pair of elements. What is the most reliable way to keep a mapping of each element in the vector? A hash table.

We reduce the searching time from O(n²) to O(n) by trading space for speed. A hash table is created precisely for this goal, it maintains active lookup in Expected-constant time. I say “expected” because if a collision happened, a lookup could degenerate to O(n²) time. But look up in hash table should be amortized O(n) time as long as the hash function was selected precisely.

A simple implementation uses a unordered_map. while iterating we check if a counterpart has existed in the hash or not. if it presents we return the pair of the value else we insert the value at that index to the hashtable.

• Learn About arrays
• Learn about vector

Code for the Two Sum problem:

#include <iostream>
#include <vector>
#include <unordered_map>

using  hashTable=std::pair<int,bool>;
using myPair=std::pair<int,int>;
using myMap= std::unordered_map<int,bool>;
using myVec=std::vector<int >;

myPair twoSum(myVec &vec, int targetSum){
   myMap hashTable;
    for(int i=0;i<vec.size();i++){
        if(hashTable.count(targetSum-vec.at(i))==1){
            return myPair (vec.at(i),targetSum-vec.at(i));
        }
        else{
            hashTable.insert(std::make_pair(vec[i], true));
        }
    }
    return std::make_pair(-1,-1);

}
int main(){
myVec vec={1,2,3,4,5,6,7,8,9};
int targetSum=20;
myPair pair;
pair=twoSum(vec,targetSum);
std::cout<<pair.first<<" "<<pair.second<<std::endl;
}