Intersection of Two Arrays II

Problem Statement

Given two arrays nums1 and nums2, return their intersection. Each element should appear as many times as it shows in both arrays, in any order.

Example

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

Two Pointer Approach

Sort both arrays, then walk two pointers together. If the values are equal, record it and advance both. Otherwise advance the pointer at the smaller value.

Complexity

• Time: O(n log n + m log m)
• Space: O(1) extra (ignoring output)

Solution Code

Python

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i = j = 0
    res = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            res.append(nums1[i])
            i += 1
            j += 1
    return res

Java

int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1); Arrays.sort(nums2);
    List<Integer> res = new ArrayList<>();
    int i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) i++;
        else if (nums1[i] > nums2[j]) j++;
        else { res.add(nums1[i]); i++; j++; }
    }
    int[] out = new int[res.size()];
    for (int k = 0; k < out.length; k++) out[k] = res.get(k);
    return out;
}

C++

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 < (int)nums1.size() && j < (int)nums2.size()) {
        if (nums1[i] < nums2[j]) i++;
        else if (nums1[i] > nums2[j]) j++;
        else { res.push_back(nums1[i]); i++; j++; }
    }
    return res;
}

Key Takeaways

• The sorted two pointer walk naturally handles duplicate counts.
• If arrays are already sorted, this beats the hash-map approach on space.
• For one very large and one small array, a hash map can be a better choice.