349. Intersection of Two Arrays - cocoder39/coco39_LC GitHub Wiki

349. Intersection of Two Arrays

a follow up is intersection of two array ii

supposing m = longer.size() and n = shorter.size()

  • Method 1: use tow sets, T = O(m), S = O(m)
  • Method 2: sort both vectors, check if elements in the shorter vector are in the longer vector through binary search, T = O(n * log m), S = O(1)
class Solution {
public:
    vector<int> intersection(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;
        for (int i = 0; i < shorter.size(); i++) {
            if (i == 0 || shorter[i] != shorter[i - 1]) {
                if (binarySearch(longer, shorter[i])) {
                    res.push_back(shorter[i]);
                }
            }
        }
        return res;
    }
private:
    bool 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) {
                return true;
            } else if (nums[mid] < n) {
                start = mid;
            } else {
                end = mid;
            }
        } 
        return nums[start] == n || nums[end] == n;
    }
};
  • Method 3 (as follows): sort then use two pointers. T = O(m * log m), S = O(1).
vector<int> intersection(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()) {
            while (i > 0 && i < nums1.size() && nums1[i] == nums1[i - 1])   i++;
            if (i >= nums1.size())  break;
            while (j > 0 && j < nums2.size() && nums2[j] == nums2[j - 1])   j++;
            if (j >= nums2.size())  break;
            
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }

follow up: intersection of k sorted arrays? As for sorted array, hash is not necessary to decrease time complexity. Use two pointer can achieve O(n) time as hash but reduce space to O(1). Here we extend two pointers to k pointers. k pointers point to each array, supposing cur_max is the max value among those k elements, then once there is an element less than cur_max, advance it and update cur_max. Until all elements are equal.

time complexity is O(k * min(sz)), space complexity is O(k)

vector<int> intersecton(vector<vector<int>>& nums) {
        if (nums.empty())   return {};

        vector<int> res;
        vector<int> pointer(nums.size());
        while (pointer[0] < nums[0].size()) {
            int high = INT_MIN;
            for (int k = 0; k < nums.size(); k++) {
                if (pointer[k] >= nums[k].size()) return res;
                high = max(high, nums[k][pointer[k]]);
            }

            bool found = true;
            for (int k = 0; k < nums.size(); k++) {
                while (pointer[k] < nums[k].size() && nums[k][pointer[k]] < high) {
                    pointer[k]++;
                }
                if (pointer[k] >= nums[k].size() || nums[k][pointer[k]] > high) {
                    found = false;
                }
                pointer[k]++; //do not forget
            }
            if (found)  res.push_back(high);
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️