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


  • 58
    S

    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;
        }
    };

  • 15
    N

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


  • 0
    S

    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}


  • 0
    V

    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)


  • 1
    S

    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;
        }
    };

  • 0

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


  • 15
    S

    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.
    .


  • 2
    X

    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.


  • 5
    B

    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).


  • 1

    @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.


  • 0

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


  • 0
    A
    This post is deleted!

  • 0
    K

    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;

  • 0
    X

    @yanchao_hust said in C++ hash table solution and sort + two pointers solution with time and space complexity:

    o point

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

    BTW, I'm also from HUST.


  • 0
    V

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


Log in to reply
 

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