Problem Description

You are given two integer arrays nums1 and nums2. Your task is to find the intersection of these two arrays - that is, find all elements that appear in both arrays.

The intersection should follow these rules:

• Each element in the result must be unique (no duplicates, even if an element appears multiple times in the original arrays)
• The elements can be returned in any order

For example:

• If nums1 = [1, 2, 2, 1] and nums2 = [2, 2], the intersection would be [2] (only one 2, since we need unique elements)
• If nums1 = [4, 9, 5] and nums2 = [9, 4, 9, 8, 4], the intersection would be [4, 9] or [9, 4] (order doesn't matter)

The solution uses Python's set operations to efficiently find the intersection. By converting both arrays to sets using set(nums1) and set(nums2), duplicate elements are automatically removed. The & operator performs set intersection, giving us all elements that exist in both sets. Finally, list() converts the resulting set back to a list format for the return value.

Intuition

When we need to find common elements between two arrays, the natural thought is to check each element in one array against all elements in the other array. However, since we need unique elements in our result, we immediately think about using a data structure that handles uniqueness automatically - a set.

The key insight is recognizing that finding the intersection of two arrays is fundamentally the same as finding the intersection of two sets. Sets have two properties that make them perfect for this problem:

1. Automatic deduplication: When we convert an array to a set, duplicate elements are automatically removed. This solves our uniqueness requirement without any extra work.

2. Built-in intersection operation: Sets have a mathematical intersection operation that gives us exactly what we need - elements that exist in both sets.

Instead of manually tracking which elements we've seen (which would require additional space for bookkeeping and logic to avoid duplicates), we can leverage Python's set operations to do all the heavy lifting. The & operator between two sets gives us their intersection in a single, efficient operation.

The approach essentially transforms the problem from "find unique common elements between two arrays" to "find the intersection of two sets" - a much simpler problem that has a direct, one-line solution. This is why set(nums1) & set(nums2) elegantly solves the entire problem, and we just need to convert the result back to a list format to match the expected return type.

Solution Approach

The reference approach mentions using a hash table or array to track elements from nums1, then iterating through nums2 to find common elements. Let's walk through both the reference approach and the provided solution:

Method 1: Hash Table/Array Approach (Reference)

1. Create a hash table or boolean array s to record which elements exist in nums1

   • If using an array, initialize an array of size 1001 (assuming element values are bounded)
   • If using a hash table, create an empty set or dictionary

2. First pass - populate the tracking structure:

   • Iterate through each element in nums1
   • Mark each element as present in s

3. Second pass - find intersection:

   • Initialize an empty result list
   • Iterate through each element x in nums2
   • If x exists in s:
     • Add x to the result
     • Remove x from s (this ensures uniqueness - we only add each element once)

4. Return the result array

Method 2: Set Operations (Provided Solution)

The provided solution uses a more concise approach with Python's built-in set operations:

return list(set(nums1) & set(nums2))

This works in three steps:

1. set(nums1) - Convert the first array to a set, removing all duplicates
2. set(nums2) - Convert the second array to a set, removing all duplicates
3. & - Perform set intersection to get elements present in both sets
4. list() - Convert the resulting set back to a list

Both approaches have similar time complexity of O(n + m) where n and m are the lengths of the two arrays. The set operation approach is more concise and leverages Python's optimized built-in operations, while the hash table approach gives more control over the process and can be easily adapted to other languages that might not have built-in set intersection operations.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given: nums1 = [4, 9, 5] and nums2 = [9, 4, 9, 8, 4]

Step 1: Convert nums1 to a set

• set(nums1) converts [4, 9, 5] to {4, 9, 5}
• No duplicates were removed since all elements were unique

Step 2: Convert nums2 to a set

• set(nums2) converts [9, 4, 9, 8, 4] to {9, 4, 8}
• Notice how the duplicate 9's and 4's are automatically removed, leaving us with only unique elements

Step 3: Find the intersection using the & operator

• {4, 9, 5} & {9, 4, 8}
• The & operator checks which elements exist in both sets:
  • 4 exists in both sets ✓
  • 9 exists in both sets ✓
  • 5 only exists in the first set ✗
  • 8 only exists in the second set ✗
• Result: {4, 9}

Step 4: Convert back to a list

• list({4, 9}) produces [4, 9] or [9, 4] (order may vary since sets are unordered)

Final Result: [4, 9]

This approach elegantly handles all the requirements:

• Uniqueness: Converting to sets automatically removes duplicates from both arrays
• Intersection: The & operator finds exactly the elements that appear in both sets
• Any order: Since sets are unordered, the result naturally can be in any order

The entire operation list(set(nums1) & set(nums2)) completes in a single line, making it both readable and efficient.

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. This is because:

• Converting nums1 to a set takes O(n) time
• Converting nums2 to a set takes O(m) time
• The set intersection operation & takes O(min(n, m)) time
• Converting the result set to a list takes O(k) time where k is the size of the intersection
• Overall: O(n) + O(m) + O(min(n, m)) + O(k) = O(n + m)

The space complexity is O(n + m) in the worst case. This is because:

• Creating a set from nums1 requires O(n) space
• Creating a set from nums2 requires O(m) space
• The intersection result requires O(min(n, m)) space
• Overall: O(n) + O(m) + O(min(n, m)) = O(n + m)

Note: The reference answer states space complexity as O(n), which could be interpreted as considering only the additional space for one set if we assume nums2's set is created temporarily and discarded, or if n >= m is assumed. However, the actual implementation creates sets for both arrays simultaneously, leading to O(n + m) space complexity.

Common Pitfalls

1. Attempting to Preserve Element Frequency

A common mistake is thinking that the intersection should preserve how many times an element appears. For instance, if nums1 = [1, 2, 2, 1] and nums2 = [2, 2], someone might expect [2, 2] as the result instead of [2].

Why this happens: Confusion with the related problem "Intersection of Two Arrays II" which does preserve element frequencies.

Solution: Remember that this problem specifically asks for unique elements. Using sets automatically handles this requirement.

2. Memory Overhead with Large Arrays

When working with very large arrays, creating multiple set copies can consume significant memory, especially if the arrays contain many unique elements.

Alternative approach to reduce memory:

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    # Use the smaller array as the base set to minimize memory
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
  
    seen = set(nums1)
    return list(seen.intersection(nums2))

3. Assuming Sorted Output

The problem states elements can be returned in any order, but developers sometimes assume the output should be sorted, leading to unnecessary sorting operations.

Why this matters: Adding sorted() increases time complexity from O(n + m) to O((n + m) log(n + m)).

4. Type Confusion with Set Operations

Using the wrong set operation or forgetting to convert back to list:

# Wrong: Returns a set instead of list
return set(nums1) & set(nums2)

# Wrong: Uses union (|) instead of intersection (&)
return list(set(nums1) | set(nums2))

Solution: Always verify you're using the intersection operator (&) and converting the final result to a list with list().