2215. Find the Difference of Two Arrays

Description

The problem is to identify the distinct elements between two lists of integers. Specifically, we need to find elements that are present in the first list but not in the second and vice versa. The output should consist of two lists: one for the unique elements in the first list and one for the unique elements in the second list.

Intuition

The intuition behind this solution is based on leveraging the properties of sets. Sets automatically handle duplicate values and allow for efficient membership testing. By converting the lists into sets, we can easily identify which elements are unique to each list by checking if an element from one set is absent in the other set.

Approach

1. Convert both input lists into sets to eliminate duplicates and allow for fast lookups.
2. Iterate through the first set and check if each element is not present in the second set. If an element is unique to the first set, add it to the result list for the first set.
3. Repeat the process for the second set by checking if its elements are absent in the first set.
4. Return a list containing the two result lists, each representing the unique elements from the respective input lists.

Complexity

Time Complexity:

O(n + m), where n is the length of the first list and m is the length of the second list. Converting the lists to sets and performing lookups in sets both run in linear time.

Space Complexity:

O(n + m) for storing the sets and the result lists.

Code

C++

class Solution {
public:
    vector> findDifference(vector& nums1, vector& nums2) {
        set set1(nums1.begin(), nums1.end());
        set set2(nums2.begin(), nums2.end());

        vector nums1Def;
        for (int n : set1) {
            if (set2.find(n) == set2.end()) {
                nums1Def.push_back(n);
            }
        }

        vector nums2Def;
        for (int n : set2) {
            if (set1.find(n) == set1.end()) {
                nums2Def.push_back(n);
            }
        }

        return {nums1Def, nums2Def};
    }
};

Python

class Solution:
    def findDifference(self, nums1, nums2):
        set1 = set(nums1)
        set2 = set(nums2)

        nums1Def = [n for n in set1 if n not in set2]
        nums2Def = [n for n in set2 if n not in set1]

        return [nums1Def, nums2Def]

Java

class Solution {
    public List> findDifference(int[] nums1, int[] nums2) {
        Set set1 = new HashSet<>();
        for (int n : nums1) {
            set1.add(n);
        }

        Set set2 = new HashSet<>();
        for (int n : nums2) {
            set2.add(n);
        }

        List nums1Def = new ArrayList<>();
        for (int n : set1) {
            if (!set2.contains(n)) {
                nums1Def.add(n);
            }
        }

        List nums2Def = new ArrayList<>();
        for (int n : set2) {
            if (!set1.contains(n)) {
                nums2Def.add(n);
            }
        }

        List> result = new ArrayList<>();
        result.add(nums1Def);
        result.add(nums2Def);
        return result;
    }
}

JavaScript

var findDifference = function (nums1, nums2) {
    let set1 = new Set(nums1)
    let set2 = new Set(nums2)

    const nums1Def = []
    for (let n of set1) {
        if (!set2.has(n)) nums1Def.push(n)
    }

    const nums2Def = []
    for (let n of set2) {
        if (!set1.has(n)) nums2Def.push(n)
    }
    return [nums1Def, nums2Def]
};