350. Intersection of Two Arrays II

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:

Method 1: HashMap

Put all elements with its frequency from nums1 to the HashMap.

Check every element in nums2.

If it is in the HashMap and its frequency is larger than 1, this element is an intersection element. 

We add it and decrease the frequency of this number by 1 in the map.
The time complexity is O(n) and the space complexity is O(n);



Code:

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new LinkedList<>();
        for (int num : nums1) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            }
            else {
                map.put(num, map.get(num) + 1);
            }
        }
        for (int num : nums2) {
            if (map.containsKey(num) && map.get(num) > 0) {
                list.add(num);
                map.put(num, map.get(num) - 1);
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int num : list) {
            res[i++] = num;
        }
        return res;
    }
}

Method 2: Two Pointers

Sort two arrays.

Use two pointers from the beginning of two arrays.

Advance one pointer if it points to a smaller number.

If two pointer points to same value elements, this number is an intersection element.

The time complexity is O(nlogn).



Code:

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> intersect = new LinkedList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            }
            else if (nums1[i] > nums2[j]) {
                j++;
            }
            else {
                intersect.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[intersect.size()];
        i = 0;
        for (int num : intersect) {
            res[i++] = num;
        }
        return res;
    }
}