LeetCode 350: Intersection of Two Arrays II - Comprehensive Solutions Guide

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection where each element appears as many times as it shows in both arrays.

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

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

Explanation

This approach: 1. Counts frequencies of elements in the smaller array 2. Iterates through the larger array, checking against counts 3. Decrements counts when matches are found

Step-by-Step Example

For nums1 = [1,2,2,1], nums2 = [2,2]: 1. Count nums1 frequencies: {1:2, 2:2} 2. Check nums2 elements: - 2 appears (count=2) → add to result, count→1 - 2 appears (count=1) → add to result, count→0 3. Final result: [2,2]

Python Implementation

Copy codefrom collections import defaultdict

def intersect(nums1: list[int], nums2: list[int]) -> list[int]:
    if len(nums1) > len(nums2):
        return intersect(nums2, nums1)  # Process smaller array first

    freq = defaultdict(int)
    for num in nums1:
        freq[num] += 1

    result = []
    for num in nums2:
        if freq[num] > 0:
            result.append(num)
            freq[num] -= 1

    return result

Complexity Analysis

• Time Complexity: O(m + n) - two passes through arrays
• Space Complexity: O(min(m,n)) - for frequency map
• Why Optimal: Efficient frequency counting with hash map

Solution 2: Sorting + Two Pointers (Alternative)

Explanation

This approach: 1. Sorts both arrays 2. Uses two pointers to find matches 3. Handles duplicates naturally through sorted order

Python Implementation

Copy codedef intersect(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:
            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 hash map
• Cons: Slower for small arrays due to sorting

Solution 3: Counter Collection (Pythonic)

Explanation

This Python-specific solution: 1. Uses Counter from collections 2. Finds intersection with element-wise minimum 3. Expands result with correct counts

Python Implementation

Copy codefrom collections import Counter

def intersect(nums1: list[int], nums2: list[int]) -> list[int]:
    counts1 = Counter(nums1)
    counts2 = Counter(nums2)
    intersection = counts1 & counts2  # Element-wise minimum
    return list(intersection.elements())

Complexity Analysis

• Time Complexity: O(m + n) - Counter operations
• Space Complexity: O(m + n) - for Counters
• Pros: Extremely concise
• Cons: Less flexible than manual implementation

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. Multiple duplicate elements

Performance Comparison

Final Recommendations

• Hash map solution is preferred for interviews
• Counter solution is great for Python in practice
• Sorting approach is good when space is constrained
• Problem teaches important frequency counting techniques