Intersection of Two Arrays II

Problem

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.

Solution

Sorting Solution: O(nlgn) time and O(n) space

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = 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 {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        return list.stream().mapToInt(a -> a).toArray();
    }
}

HashMap Solution: O(n) time and O(n) space

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) map.put(num, map.getOrDefault(num, 0) + 1);
        for (int num : nums2) {
            Integer intersection = map.get(num); //To check null, we must init with Integer here 
            if (intersection != null && intersection > 0) {
                list.add(num);
                map.put(num, intersection - 1);
            }
        }
        return list.stream().mapToInt(a -> a).toArray();
    }
}

Analysis

This is revision problem of Intersection of Two Arrays
The difference is that we need to return the original intersection instead of distinct numbers
Therefore, we cannot use super concise Java 8 solution
The first solution is similar to the idea in Intersection of Two Arrays
The second solution use Hash Map to store the number and its count in nums1
Then we loop nums2 and get the count of each number
If there is intersection, we add it to our list and update the count by decrement one
At the end, we use list.stream().mapToInt(a->a).toArray() to convert list to primitive type of array int[]