Find the Difference of Two Arrays

How it works

Many programming languages provide built-in set difference operations. The set difference A - B returns all elements in A that are not in B. This is exactly what the problem asks for, so we can leverage these optimized library functions for a clean, concise solution.

Steps

1. Convert both arrays to sets.
2. Compute the set difference of set1 minus set2 to get elements unique to nums1.
3. Compute the set difference of set2 minus set1 to get elements unique to nums2.
4. Convert both results to lists and return them.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n + m)

Where n is the size of the array nums1 and m is the size of the array nums2.

Things to watch for

Returning Duplicate Values in the Result

The problem asks for distinct integers. If you iterate through the original arrays instead of sets, you might add the same value multiple times to your result. Always use sets or track seen values to ensure each element appears only once in the output.

Confusing Which Array Each Result Belongs To

The output is a list of two lists: the first contains elements in nums1 but not in nums2, and the second contains elements in nums2 but not in nums1. Swapping these leads to incorrect results. Double-check which difference operation corresponds to which result list.

from typing import List

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        numSet1, numSet2 = set(nums1), set(nums2)
        return [list(numSet1 - numSet2), list(numSet2 - numSet1)]

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res1, res2;
        set<int> numSet1(begin(nums1), end(nums1)), numSet2(begin(nums2), end(nums2));

        set_difference(begin(numSet1), end(numSet1), begin(numSet2), end(numSet2), back_inserter(res1));
        set_difference(begin(numSet2), end(numSet2), begin(numSet1), end(numSet1), back_inserter(res2));

        return {res1, res2};
    }
};