intersection-of-two-arrays.cpp

// Time:  O(m + n)
// Space: O(min(m, n))

// Hash solution.
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersection(nums2, nums1);
        }

        unordered_set<int> lookup{nums1.cbegin(), nums1.cend()};

        vector<int> result;
        for (const auto& i : nums2) {
            if (lookup.count(i)) {
                result.emplace_back(i);
                lookup.erase(i);
            }
        }

        return result;
    }
};


// Time:  O(max(m, n) * log(max(m, n)))
// Space: O(1)
// Binary search solution.
class Solution2 {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersection(nums2, nums1);
        }

        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        vector<int> result;
        auto it = nums2.cbegin();
        for (const auto& i : nums1) {
            it = lower_bound(it, nums2.cend(), i);
            if (it != nums2.end() && *it == i) {
                result.emplace_back(*it);
                it = upper_bound(it, nums2.cend(), i);
            }
        }
        
        return result;
    }
};


// Time:  O(max(m, n) * log(max(m, n)))
// Space: O(1)
// Two pointers solution.
class Solution3 {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto it1 = nums1.cbegin(), it2 = nums2.cbegin();
        while (it1 != nums1.cend() && it2 != nums2.cend()) {
            if (*it1 < *it2) {
                ++it1;
            } else if (*it1 > *it2) {
                ++it2;
            } else {
                if (result.empty() || result.back() != *it1) {
                    result.emplace_back(*it1);
                }
                ++it1, ++it2;
            }
        }
        return result;
    }
};

// Time:  O(mlogm + nlogn)
// Space: O(m + n)
class Solution4 {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        sort(begin(nums1), end(nums1)); sort(begin(nums2), end(nums2));
        set_intersection(cbegin(nums1), cend(nums1), cbegin(nums2), cend(nums2), back_inserter(result));
        result.erase(unique(begin(result), end(result)), end(result));
        return result;
    }
};