350. Intersection of Two Arrays II - cocoder39/coco39_LC GitHub Wiki

350. Intersection of Two Arrays II

method 1 : use multiset, time is O(n) and space is O(n). or use unordered_map to record frequency of each number

tip: st.erase(it) would erase one element while erase(num) would erase all elements that are equal to num

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int> st;
        for (auto num : nums1) {
            st.insert(num);
        }
        
        vector<int> res;
        for (auto num : nums2) {
            auto it = st.find(num);
            if (it != st.end()) {
                res.push_back(num);
                st.erase(it);
            }
        }
        return res;
    }

method 2, sort then two pointers. time is O(n * log n) and space is O(1)

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        vector<int> res;
        int i = 0, j = 0;
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }

method 3 : sort then binary search. time is O(n log n) and space is O(1)

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> longer, shorter;
        if (nums1.size() < nums2.size()) {
            longer = nums2;
            shorter = nums1;
        } else {
            longer = nums1;
            shorter = nums2;
        }
        sort(longer.begin(), longer.end());
        sort(shorter.begin(), shorter.end());

        vector<int> res;
        int idx1 = 0;
        while (idx1 < shorter.size()) {
            int num1 = 0;
            for (int i = idx1; i < shorter.size() && shorter[i] == shorter[idx1]; i++) {
                num1++;
            }
            
            int idx2 = binarySearch(longer, shorter[idx1]);
            if (idx2 != -1) {
                int num2 = 0;
                for (int i = idx2; i < longer.size() && longer[i] == longer[idx2]; i++) {
                    num2++;
                }  
                
                for (int i = 0; i < num1 && i < num2; i++) {
                    res.push_back(shorter[idx1]);
                }
            } 
            idx1 += num1;
        }
        return res;
    }
private:
    int binarySearch(vector<int>& nums, int n) {
        int start = 0, end = nums.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= n) {
                end = mid;
            } else {
                start = mid;
            }
        } 
        
        if (nums[start] == n) {
            return start;
        } else if (nums[end] == n) {
            return end;
        } else {
            return -1;
        }
    }
};
  • follow up 1: what if the given array is already sorted? use hash takes O(n) time but O(n) memory; use two pointers takes O(n) time and O(1) memory; using binary search takes O(n * log n) time and O(1) memory. Thus prefer two pointers
  • follow up 2: what if n1 << n2? using hash takes O(n1) time and O(n2) memory is memory is not an issue; otherwise takes O(n2) time and O(n1) memory. using two pointers takes O(n2 * log n2) time; if already sorted, takes O(n1) time. using binary search takes O(n2 * log n2) time; if already sorted, takes O(n1 * log n2) time. Thus if sorted using two pointers; else if memory is not an issue using hash; else using either two pointers or binary search.
  • follow up 3: what if nums2 are on disk, and memory is limited? if memory can hold nums1, use hash; otherwise, external sort both vectors on disk, fetch 1G data from both vectors, apply two pointers to data in memory, then fetch another 2G...
⚠️ **GitHub.com Fallback** ⚠️