LeetCode 349: Intersection of Two Arrays - Comprehensive Solutions Guide

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection (elements present in both arrays). Each element in the result must be unique.

Copy codeInput: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Explanation

This approach: 1. Converts one array to a set for O(1) lookups 2. Iterates through the second array, checking for matches 3. Uses another set to avoid duplicates in result

Step-by-Step Example

For nums1 = [4,9,5], nums2 = [9,4,9,8,4]: 1. Convert nums1 to set: {4,9,5} 2. Check nums2 elements: - 9 in set → add to result - 4 in set → add to result - 9 already in result - 8 not in set - 4 already in result 3. Final result: [9,4]

Python Implementation

Copy codedef intersection(nums1: list[int], nums2: list[int]) -> list[int]:
    set1 = set(nums1)
    result = set()

    for num in nums2:
        if num in set1:
            result.add(num)

    return list(result)

Complexity Analysis

• Time Complexity: O(m + n) - converting to set and iterating
• Space Complexity: O(m + n) - for sets storage
• Why Optimal: Efficient lookup with hash sets

Solution 2: Built-in Set Intersection (Pythonic)

Explanation

This Python-specific solution: 1. Converts both arrays to sets 2. Uses set intersection operation 3. Converts back to list

Python Implementation

Copy codedef intersection(nums1: list[int], nums2: list[int]) -> list[int]:
    return list(set(nums1) & set(nums2))

Complexity Analysis

• Time Complexity: O(m + n) - set conversion and intersection
• Space Complexity: O(m + n) - for sets storage
• Pros: Extremely concise
• Cons: Less flexible than manual implementation

Solution 3: Sorting + Two Pointers (Alternative)

Explanation

This approach: 1. Sorts both arrays 2. Uses two pointers to find matches 3. Skips duplicates during comparison

Python Implementation

Copy codedef intersection(nums1: list[int], nums2: list[int]) -> list[int]:
    nums1.sort()
    nums2.sort()
    i = j = 0
    result = []

    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            if not result or nums1[i] != result[-1]:
                result.append(nums1[i])
            i += 1
            j += 1

    return result

Complexity Analysis

• Time Complexity: O(m log m + n log n) - sorting dominates
• Space Complexity: O(1) additional space (excluding result)
• Pros: No extra space for sets
• Cons: Slower for small arrays due to sorting

Edge Cases to Consider

1. Empty input arrays
2. No intersection elements
3. All elements identical in both arrays
4. One array much larger than the other
5. Duplicate elements within single array

Performance Comparison

Final Recommendations

• Hash set solution is preferred for interviews
• Built-in set intersection is great for Python in practice
• Sorting approach is good when space is constrained
• Problem teaches important set operations