Problem Description

Given two integer arrays, nums1 and nums2, you are asked to find the distinct elements that are present in one array but not in the other. Specifically, return a list containing two lists:

• The first list contains all distinct integers from nums1 that are not present in nums2.
• The second list contains all distinct integers from nums2 that are not present in nums1.

Constraints:

• Each input array may have duplicate values, but results must only include unique values.
• Each element should only appear once in its respective result list.
• There is always at least one valid answer.
• Do not reuse elements between the two output lists.

Thought Process

To solve this problem, we need to compare two arrays and find which unique elements are exclusive to each array. The first idea that comes to mind is to check, for every number in nums1, whether it is absent in nums2, and vice versa. This is a brute-force approach, where for each element in one array, we check all elements of the other array.

However, this brute-force method is inefficient, especially for large arrays, because it requires nested loops, leading to high time complexity. Instead, we can use data structures that allow for fast lookups, like sets, which provide constant-time operations for checking membership and for eliminating duplicates.

By converting both arrays to sets, we can easily find the differences between them, which gives us the distinct elements unique to each array. This shift from brute-force to using sets significantly optimizes our solution.

Solution Approach

Let's break down the optimized solution step-by-step:

1. Remove Duplicates:
   • Convert both nums1 and nums2 into sets. This automatically removes duplicate values and allows for efficient lookups.
2. Find Unique Elements:
   • To find elements unique to nums1, subtract the set of nums2 from nums1 (i.e., set1 - set2).
   • To find elements unique to nums2, subtract the set of nums1 from nums2 (i.e., set2 - set1).
3. Convert Sets Back to Lists:
   • Since the result must be lists, convert the sets back to lists before returning.
4. Return the Result:
   • Return a list of the two lists as specified.

We use sets because they are optimized for checking whether an element exists (O(1) on average) and for set operations like difference, which are also efficient.

Example Walkthrough

Let's walk through a sample input:

Input:
nums1 = [1, 2, 3, 3]
nums2 = [2, 4, 6]

1. Convert to Sets:
   set1 = {1, 2, 3}
set2 = {2, 4, 6}
2. Find Unique to nums1:
   set1 - set2 = {1, 3} (since 1 and 3 are not in set2)
3. Find Unique to nums2:
   set2 - set1 = {4, 6} (since 4 and 6 are not in set1)
4. Convert to Lists and Return:
   [[1, 3], [4, 6]]

Each step ensures that only unique values are included and that the result meets the problem's requirements.

Time and Space Complexity

Brute-force Approach:

• For each element in nums1, check if it is in nums2 (O(m * n), where m and n are the lengths of the arrays).
• The same is done for nums2 vs nums1.
• This is inefficient for large arrays.

• Converting arrays to sets: O(m + n)
• Set difference operations: O(m + n)
• Overall time complexity: O(m + n)
• Space complexity: O(m + n) for storing the sets.

The optimized solution is efficient and suitable for large input sizes.

Code Implementation

class Solution:
    def findDifference(self, nums1, nums2):
        set1 = set(nums1)
        set2 = set(nums2)
        return [list(set1 - set2), list(set2 - set1)]
      

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        vector<int> diff1, diff2;
        for (int n : set1) {
            if (set2.find(n) == set2.end()) diff1.push_back(n);
        }
        for (int n : set2) {
            if (set1.find(n) == set1.end()) diff2.push_back(n);
        }
        return {diff1, diff2};
    }
};
      

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int n : nums1) set1.add(n);
        for (int n : nums2) set2.add(n);
        List<Integer> diff1 = new ArrayList<>();
        List<Integer> diff2 = new ArrayList<>();
        for (int n : set1) {
            if (!set2.contains(n)) diff1.add(n);
        }
        for (int n : set2) {
            if (!set1.contains(n)) diff2.add(n);
        }
        List<List<Integer>> result = new ArrayList<>();
        result.add(diff1);
        result.add(diff2);
        return result;
    }
}
      

var findDifference = function(nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);
    let diff1 = [...set1].filter(x => !set2.has(x));
    let diff2 = [...set2].filter(x => !set1.has(x));
    return [diff1, diff2];
};
      

Summary

The key to solving the "Find the Difference of Two Arrays" problem efficiently is to leverage sets for their unique-value storage and fast membership checks. By using set difference operations, we can quickly and elegantly find the unique elements in each array, ensuring no duplicates and optimal performance. This approach is both simple and powerful, making the solution easy to understand and implement.