Problem Description

You are given two integer arrays nums1 and nums2, both 0-indexed. Your task is to find the differences between these two arrays.

You need to return a list containing exactly 2 lists:

• The first list (answer[0]) should contain all unique integers that appear in nums1 but not in nums2
• The second list (answer[1]) should contain all unique integers that appear in nums2 but not in nums1

Key requirements:

• Only distinct integers should be included (no duplicates in the result lists)
• The integers in each result list can be returned in any order
• An integer should only appear in one of the result lists based on which array it's exclusive to

For example, if nums1 = [1,2,3] and nums2 = [2,4,6]:

• Numbers exclusive to nums1: [1,3] (since 2 appears in both)
• Numbers exclusive to nums2: [4,6] (since 2 appears in both)
• Result: [[1,3], [4,6]]

The solution uses sets to efficiently handle duplicates and find differences. By converting both arrays to sets (s1 and s2), we can use set difference operations: s1 - s2 gives elements in s1 but not in s2, and s2 - s1 gives elements in s2 but not in s1. These set differences are then converted back to lists for the final answer.

Intuition

When we need to find elements that exist in one collection but not in another, the natural approach is to check membership. For each element in the first array, we'd ask: "Is this element present in the second array?" If not, it belongs to our first result list.

The challenge here is that both arrays might contain duplicates, but we only want distinct values in our results. If we used the arrays directly, we'd need to:

1. Track which elements we've already added to avoid duplicates
2. Check if each element exists in the other array (potentially scanning through many duplicates)

This leads us to think about sets - a data structure that automatically handles uniqueness and provides efficient membership checking. When we convert nums1 to a set, all duplicates are removed automatically. The same goes for nums2.

Once we have sets, finding exclusive elements becomes straightforward. The mathematical concept of set difference perfectly captures what we need: A - B gives us all elements in set A that are not in set B. This is exactly what the problem asks for - elements in nums1 not in nums2.

The beauty of using sets is that the set difference operation s1 - s2 does all the heavy lifting in one go:

• It iterates through elements in s1
• Checks if each element exists in s2 (with O(1) average time complexity)
• Returns only those elements not found in s2

By applying this operation twice (s1 - s2 and s2 - s1), we get both lists of exclusive elements efficiently, without writing explicit loops or membership checks ourselves.

Solution Approach

The implementation uses hash tables (specifically Python sets) to efficiently find the differences between two arrays.

Step 1: Convert Arrays to Sets

s1, s2 = set(nums1), set(nums2)

We create two sets from the input arrays. This conversion:

• Removes all duplicate elements automatically
• Enables O(1) average-time membership checking
• Allows us to use set operations

For example, if nums1 = [1,2,2,3], then s1 = {1,2,3} (duplicates removed).

Step 2: Calculate Set Differences

return [list(s1 - s2), list(s2 - s1)]

We use the set difference operation twice:

• s1 - s2: Returns elements in s1 that are not in s2
• s2 - s1: Returns elements in s2 that are not in s1

The set difference operation internally:

1. Iterates through each element in the first set
2. Checks if that element exists in the second set (hash table lookup)
3. Includes the element in the result only if it's not found

Step 3: Convert Results to Lists Since the problem expects lists as output, we convert each set difference result back to a list using list().

Time Complexity Analysis:

• Converting arrays to sets: O(n + m) where n and m are the lengths of nums1 and nums2
• Set difference operations: O(n) for s1 - s2 and O(m) for s2 - s1
• Overall: O(n + m)

Space Complexity:

• Two sets storing unique elements: O(n + m) in the worst case when all elements are unique
• Output lists: O(n + m) in the worst case
• Overall: O(n + m)

This approach is optimal because we only traverse each array once and leverage the hash table's constant-time lookups to avoid nested loops.

Example Walkthrough

Let's walk through the solution with a concrete example:

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

Step 1: Convert arrays to sets

• s1 = set([1,2,3,3]) → s1 = {1,2,3} (duplicate 3 removed)
• s2 = set([2,4,6,2]) → s2 = {2,4,6} (duplicate 2 removed)

Step 2: Calculate set differences

For s1 - s2 (elements in s1 not in s2):

• Check 1: Is 1 in s2? No → Include 1
• Check 2: Is 2 in s2? Yes → Skip
• Check 3: Is 3 in s2? No → Include 3
• Result: {1,3}

For s2 - s1 (elements in s2 not in s1):

• Check 2: Is 2 in s1? Yes → Skip
• Check 4: Is 4 in s1? No → Include 4
• Check 6: Is 6 in s1? No → Include 6
• Result: {4,6}

Step 3: Convert to lists and return

• list({1,3}) → [1,3]
• list({4,6}) → [4,6]
• Final answer: [[1,3], [4,6]]

The solution correctly identifies:

• Numbers unique to nums1: 1 and 3 (note that duplicate 3s in the original array appear only once)
• Numbers unique to nums2: 4 and 6 (2 is excluded since it appears in both arrays)

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the length of nums1 and m is the length of nums2. Creating set(nums1) takes O(n) time, creating set(nums2) takes O(m) time, and the set difference operations s1 - s2 and s2 - s1 each take O(min(n, m)) time in the worst case. Converting the results to lists takes O(n) and O(m) time respectively. Overall, this simplifies to O(n + m).

The space complexity is O(n + m). The sets s1 and s2 require O(n) and O(m) space respectively. The output lists also require space proportional to the number of unique elements in each set difference, which in the worst case is O(n) and O(m). Therefore, the total space complexity is O(n + m).

Note: If we consider n and m to be approximately equal (both representing the general length of the input arrays), we can simplify both complexities to O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Remove Duplicates from the Result

A common mistake is trying to solve this problem without using sets, leading to duplicate values in the output lists.

Incorrect Approach:

def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
    result1 = []
    result2 = []
  
    # This will include duplicates!
    for num in nums1:
        if num not in nums2:
            result1.append(num)
  
    for num in nums2:
        if num not in nums1:
            result2.append(num)
  
    return [result1, result2]

Problem: If nums1 = [1,2,2,3] and nums2 = [2,4,6], this would return [[1,2,3], [4,6]] with duplicate 2s in the first list.

Solution: Either use sets from the beginning or deduplicate the results:

# Option 1: Deduplicate while building results
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
    set2 = set(nums2)
    result1 = []
    seen1 = set()
  
    for num in nums1:
        if num not in set2 and num not in seen1:
            result1.append(num)
            seen1.add(num)
  
    # Similar logic for nums2...

2. Using Lists for Membership Testing (Performance Issue)

Inefficient Approach:

def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
    # Using lists for 'in' operations is O(n) per check!
    unique1 = list(set(nums1))
    unique2 = list(set(nums2))
  
    result1 = [x for x in unique1 if x not in nums2]  # O(n*m) complexity
    result2 = [x for x in unique2 if x not in nums1]  # O(n*m) complexity
  
    return [result1, result2]

Problem: The in operator on lists has O(n) time complexity, making the overall solution O(n*m) instead of O(n+m).

Solution: Always convert to sets before doing membership testing:

def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
    set1, set2 = set(nums1), set(nums2)
    return [list(set1 - set2), list(set2 - set1)]

3. Modifying Input Arrays During Processing

Dangerous Approach:

def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
    # Don't modify input arrays!
    nums1 = list(set(nums1))  # This reassigns but could be problematic
    nums2 = list(set(nums2))
  
    # If you accidentally did nums1.clear() or nums1[:] = [], 
    # it would affect the original array

Solution: Always work with copies or new data structures without modifying the original inputs.