2215. Find the Difference of Two Arrays

[songyy5517]

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

• answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
• answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Intuition This problem is to find the exclusive elements in each array. A simple idea is to use two hashsets to store the elements of two arrays respectively. Then for each hashset, we remove the elements appearing in the other array (not hashset). Finally, we combine these two hashsets into a List and return the list.

[songyy5517]

Approach: HashSet

1. Exception handling;
2. Define two hashsets and put all elements of two arrays into the two hashsets respectively;
3. For each hashset, remove the elements appearing in another array.
4. Convert the two hashsets into a List, and return.

Complexity Analysis

• Time complexity: $O(M+N)$ , $M$ and $N$ are the size of two arrays respectively. The add and remove operations of two hashsets takes $O(M+N)$ time;
• Space complexity: $O(M+N)$ , additionally define two hashsets which takes the space of $O(M)$ and $O(N)$ respectively.

[songyy5517]

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        // Intuition: HashMap
        // 1. Exception handling
        if (nums1 == null || nums2 == null)
            return new ArrayList();

        // 2. Define variables
        HashSet<Integer> hs1 = new HashSet();
        HashSet<Integer> hs2 = new HashSet();

        for (int i : nums1)
            hs1.add(i);

        for (int i : nums2)
            hs2.add(i);

        for (int i : nums1)
            hs2.remove(i);

        for (int i : nums2)
            hs1.remove(i);

        return List.of(List.copyOf(hs1), List.copyOf(hs2));
    }
}

[songyy5517]

2024/5/16

• hs.remove(num): remove elements from hashset;
• List.copyOf: generate List from Collection;
• List.of: generate a List with specific elments.