# C++ hash table solution and sort + two pointers solution with time and space complexity

• m: nums1.size n: nums2.size

Hash table solution:
Time: O(m + n) Space: O(m + n)

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> dict;
vector<int> res;
for(int i = 0; i < (int)nums1.size(); i++) dict[nums1[i]]++;
for(int i = 0; i < (int)nums2.size(); i++)
if(--dict[nums2[i]] >= 0) res.push_back(nums2[i]);
return res;
}
};
``````

Hash table solution2:
Time: O(m + n) Space: O(m)

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> dict;
vector<int> res;
for(int i = 0; i < (int)nums1.size(); i++) dict[nums1[i]]++;
for(int i = 0; i < (int)nums2.size(); i++)
if(dict.find(nums2[i]) != dict.end() && --dict[nums2[i]] >= 0) res.push_back(nums2[i]);
return res;
}
};
``````

Sort and two pointers Solution:
Time: O(max(m, n) log(max(m, n))) Space: O(m + n)

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int n1 = (int)nums1.size(), n2 = (int)nums2.size();
int i1 = 0, i2 = 0;
vector<int> res;
while(i1 < n1 && i2 < n2){
if(nums1[i1] == nums2[i2]) {
res.push_back(nums1[i1]);
i1++;
i2++;
}
else if(nums1[i1] > nums2[i2]){
i2++;
}
else{
i1++;
}
}
return res;
}
};``````

• why hashtable solution space is m+n????? It is m or n

• run the program step by step. you will find the result when they are all distinct number and don't have intersection. e.g. nums1 = {1,2,3,4,5}, nums2 = {6,7,8,9,10}

• I think you count the 'res' vector as space complexity also , i'm not sure if it's necessary. In terms of extra/auxiliary space , it's indeed either m or n , not both (for hashtable solution)

• yes, if we do a check before --, the space complexity is O(m).

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> dict;
vector<int> res;
for(int i = 0; i < (int)nums1.size(); i++) dict[nums1[i]]++;
for(int i = 0; i < (int)nums2.size(); i++)
if(dict.find(nums2[i]) != dict.end() && --dict[nums2[i]] >= 0) res.push_back(nums2[i]);
return res;
}
};``````

• I don't understand why the space complexity is different for solution 1 & 2??

• Based on C++ map mechanism, if a key is not exist, access the key will assign a default value to the key. so if you simply test if map[key] is 0 or not by using "if (map[key] == 0)" without testing if the key is in the map. you will consume extra space....you could avoid allocate extra space either by find or count method. I usually use count, it is more concise.
.

• I think the Space for Sort method is O(1), you only need 2 pointers. Input & output Spaces should not be included since they are all the same for different methods.

• For the sort and two pointers Solution, I think the time complexity should be O(max(m+n, mlgm, nlgn)). The while loop might traverse both nums1 and nums2 in the worst case(and two sorts cost mlgm and nlgn respectively).

• @xsh6528 not O(1), for the sort and two pointers solution the space complexity should be O(min(m,n)) since there may be at most min(m,n) elements are in common.

• @Burlesque1 I think usually m+n is less than mlogm or nlogn，so it is unnecessary to consider m+n term

• This post is deleted!

• Here is a little smarter one.

``````        if (nums1.size() == 0 || nums2.size() == 0) return vector<int>(0);

unordered_map<int, int> numMap;
vector<int> Result;
if (nums1.size() > nums2.size())
swap(nums1, nums2);

for (int i : nums1)
numMap[i]++;

for (int i : nums2)
{
if (numMap.find(i) != numMap.end() && numMap[i]-- > 0)
Result.push_back(i);
}

return Result;``````

• o point

As I said, In a coding interview, output space doesn't count into space complexity.

BTW, I'm also from HUST.

• @xsh6528 u are right,there is no auxiliary space usead

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.