Intersection of Two Arrays II

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

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

Challenge:

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

What if nums1's size is small compared to num2'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?

Example:

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

Solution:

Similar to Merge Sort. We sort both nums1 and nums2 first, and then use two pointers to find the same value from two arrays. If we found the same value in both two arrays, we push it to result list.

If the array is sorted, the algorithm will run in O(m) time where (m < n and m, n are length of nums1 and nums2).

If nums2 are two large to store, we could store each element of nums1 into an HashMap<Integer, Integer>, the key of the hashmap is the value of that element, the value of the hashmap is the count of the duplications of the corresponding value.

Code:

public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return new int[] {};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int m = nums1.length;
        int n = nums2.length;
        List<Integer> hset = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (nums1[i] == nums2[j]) {
                hset.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                i++;
            }
        }
        int[] res = new int[hset.size()];
        int counter = 0;
        for (int x : hset) {
            res[counter++] = x;
        }
        return res;
    }
}