Intersection of Two Arrays II

Problem:

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        int size1 = nums1.size(), size2 = nums2.size();
        if (size1 == 0 || size2 == 0) {
            return ans;
        }
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        while (i < size1 && j < size2) {
            if (nums1[i] == nums2[j]) {
                ans.push_back(nums1[i]);
                i++; j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};

=============

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

Solution 1, i.e., sorting, would be better since it does not need extra memory.

What if nums1’s size is small compared to num2’s size? Which algorithm is better?

• If two arrays are sorted, we could use binary search, i.e., for each element in the shorter array, search in the longer one. So the overall time complexity is O(nlogm), where n is the length of the shorter array, and m is the length of the longer array. Note that this is better than Solution 1 since the time complexity is O(n + m) in the worst case.

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

• If the two arrays have relatively the same length, we can use external sort to sort out the two arrays in the disk. Then load chunks of each array into the memory and compare, by using the method 1.
• If one array is too short while the other is long, in this case, if memory is limited and nums2 is stored in disk, partition it and send portions of nums2 piece by piece. keep a pointer for nums1 indicating the current position, and it should be working fine~
• Another method is, store the larger array into disk, and for each element in the shorter array, use “Exponential Search” and search in the longer array.