350. Intersection of Two Arrays II

1. Intersection of Two Arrays II

Question

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Algorithm

This question is pretty easy, no order constrain, so we could use map to count the numbers.

We first count the number count in nums1 in a map, and then decrease the number count in the map by loop nums2, when there are still count left in the map mean we have corresponding numbers in both arrays. And we could record such number once in the result list.

Code

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

Follow up1

What is the array is sorted ? Any better algorithm?

In my view, we may get rid of the extra space, we go through both the array at the same time and look for their first same elements and last same elements , handling the repeat elements in the middle.

Code

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            ++i;
        } else if (nums1[i] > nums2[j]) {
            ++j;
        } else {
            nums1[k++] = nums1[i++];
            ++j;
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

Follow up2

If nums1's size is small compared to the other, which algorithm is better?

I think map would be better considering the space , we construct the map based on the small size array. Time complex is O(n) for both algorithm.

Follow up3

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?

1. If nums1 fits into memory, load it into memory and use approach 1 ;
2. If both arrays cannot fit into the memory, split the range into segments and call the approach1(modified to accommodate to collect specified segments)
   1. Or use external sort for both array and modify approach 2 to load and process array sequentially.