How to Compute the Intersection of Two Arrays using Sorting + Two Pointer Algorithm?

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

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

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?

You can easily use the hash map to do the counting and solve the problem: The Intersection Algorithm of Two Arrays using Hash Maps in C++/Java/JavaScript

Sort and Two Pointer Algorithm

Given two arrays, we can sort them, in O(nlogN) time. Then we define two pointers i and j pointing to the begining of these two arrays respectively.

Then, by comparing the values at both arrays pointed, we move the pointer forward (to the right) if it is less than another. If it is equal, we can push the value to the intersection result vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

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

The space complexity is O(1) constant (excluding the result vector), and the time complexity is dominated by the sorting, which takes O(nlogN).

–EOF (The Ultimate Computing & Technology Blog) —