Problem Description

You are given two integer arrays nums1 and nums2. Your task is to find the intersection of these two arrays and return it as a new array.

The intersection should include all elements that appear in both arrays, and each element should appear in the result as many times as it appears in both arrays (taking the minimum count from each array). For example, if a number appears 3 times in nums1 and 2 times in nums2, it should appear 2 times in the result.

The elements in the result array can be returned in any order.

Example scenarios:

• If nums1 = [1,2,2,1] and nums2 = [2,2], the intersection would be [2,2] because the number 2 appears twice in both arrays.
• 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) because 4 appears once in nums1 and twice in nums2 (so we take 1), and 9 appears once in nums1 and twice in nums2 (so we take 1).

The solution uses a hash table to count occurrences of elements in nums1. Then it iterates through nums2, and for each element that exists in the hash table with a count greater than 0, it adds that element to the result and decrements its count in the hash table. This ensures each common element is included the correct number of times in the intersection.

Intuition

The key insight is that we need to track how many times each element appears in both arrays and include the minimum count in our result.

Think of it like comparing two shopping lists. If your first list has 3 apples and your second list has 2 apples, the common items between both lists would be 2 apples (the smaller count).

To efficiently track and compare these counts, we can use a hash table (Counter in Python) to store the frequency of each element from the first array. This gives us O(1) lookup time for checking if an element exists and what its count is.

As we iterate through the second array, for each element we encounter:

• If it exists in our hash table (meaning it was in the first array) and still has a positive count, it's part of the intersection
• We add it to our result and decrement its count in the hash table
• Decrementing ensures we don't include more occurrences than what exists in the first array

This approach is more efficient than sorting both arrays or using nested loops. By using a hash table, we avoid repeatedly searching through nums1 for each element in nums2. The decrementing mechanism naturally handles the "minimum count" requirement - once we've used up all occurrences from nums1, that element won't be added to the result anymore, even if it appears more times in nums2.

Solution Approach

The implementation uses a hash table to efficiently find the intersection of two arrays with duplicates.

Step 1: Count elements in the first array

cnt = Counter(nums1)

We use Python's Counter class (a specialized dictionary) to count the frequency of each element in nums1. For example, if nums1 = [1,2,2,1], then cnt becomes {1: 2, 2: 2}.

Step 2: Initialize the result array

ans = []

Create an empty list to store the intersection elements.

Step 3: Iterate through the second array

for x in nums2:
    if cnt[x]:
        ans.append(x)
        cnt[x] -= 1

For each element x in nums2:

• Check if cnt[x] is greater than 0 (meaning x exists in nums1 and hasn't been fully used)
• If true, add x to the answer array
• Decrement cnt[x] by 1 to mark that we've used one occurrence of this element

The condition if cnt[x] works because:

• If x exists in the counter with a positive value, it evaluates to True
• If x doesn't exist or has value 0, it evaluates to False

Step 4: Return the result

return ans

Time Complexity: O(m + n) where m and n are the lengths of nums1 and nums2 respectively. We traverse each array once.

Space Complexity: O(min(m, n)) for the hash table, as it stores at most the unique elements from the smaller array.

Example Walkthrough

Let's walk through the solution with a concrete example where nums1 = [1,2,2,1] and nums2 = [2,2,3].

Step 1: Build frequency counter for nums1

• Process nums1 = [1,2,2,1]
• Counter becomes: {1: 2, 2: 2}
• This tells us that 1 appears twice and 2 appears twice in nums1

Step 2: Process nums2 element by element

Processing first element (2):

• Check: Is cnt[2] > 0? Yes, cnt[2] = 2
• Add 2 to result: ans = [2]
• Decrement counter: cnt[2] = 2 - 1 = 1
• Counter now: {1: 2, 2: 1}

Processing second element (2):

• Check: Is cnt[2] > 0? Yes, cnt[2] = 1
• Add 2 to result: ans = [2, 2]
• Decrement counter: cnt[2] = 1 - 1 = 0
• Counter now: {1: 2, 2: 0}

Processing third element (3):

• Check: Is cnt[3] > 0? No, cnt[3] = 0 (doesn't exist)
• Skip this element
• Result remains: ans = [2, 2]

Step 3: Return result

• Final answer: [2, 2]

The algorithm correctly identifies that 2 appears twice in both arrays (twice in nums1, twice in nums2), so it includes 2 twice in the intersection. The element 1 from nums1 and element 3 from nums2 don't appear in both arrays, so they're excluded from the result.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the length of nums1 and n is the length of nums2. This is because:

• Creating the Counter from nums1 takes O(m) time
• Iterating through each element in nums2 takes O(n) time
• Each dictionary lookup and update operation inside the loop takes O(1) time on average
• Therefore, the total time complexity is O(m) + O(n) = O(m + n)

The space complexity is O(m), where m is the length of nums1. This is because:

• The Counter object cnt stores at most m elements (all unique elements from nums1)
• The output list ans stores at most min(m, n) elements, which is bounded by O(m)
• Therefore, the dominant space usage is O(m)

Common Pitfalls

1. Accessing Non-existent Keys in Dictionary

A common mistake is directly checking cnt[x] when x might not exist in the counter/dictionary, which can raise a KeyError in standard dictionaries.

Problematic Code:

# Using a regular dict instead of Counter
frequency_map = {}
for num in nums1:
    frequency_map[num] = frequency_map.get(num, 0) + 1

for num in nums2:
    if frequency_map[num] > 0:  # KeyError if num not in frequency_map!
        result.append(num)
        frequency_map[num] -= 1

Solution: Use proper existence checking or leverage Counter's default behavior:

# Option 1: Check key existence first
if num in frequency_map and frequency_map[num] > 0:
    result.append(num)
    frequency_map[num] -= 1

# Option 2: Use get() method
if frequency_map.get(num, 0) > 0:
    result.append(num)
    frequency_map[num] -= 1

# Option 3: Use Counter (handles missing keys gracefully)
cnt = Counter(nums1)
if cnt[num]:  # Counter returns 0 for missing keys
    result.append(num)
    cnt[num] -= 1

2. Modifying the Wrong Array's Frequency

Another pitfall is accidentally counting elements from nums2 or modifying the wrong array's frequency map, especially when trying to optimize by counting the smaller array.

Problematic Code:

# Trying to optimize but introducing a bug
if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1  # Swap arrays
  
cnt = Counter(nums1)
result = []

# Bug: Still iterating through the original nums2 reference
for num in nums2:  # This is now the longer array!
    if cnt[num]:
        result.append(num)
        cnt[num] -= 1

Solution: Be consistent with which array you count and which you iterate:

# Correct optimization approach
if len(nums1) > len(nums2):
    return self.intersect(nums2, nums1)  # Recursive call with swapped parameters
  
# Or handle the swap more carefully
cnt = Counter(nums1)
result = []
for num in nums2:
    if cnt[num]:
        result.append(num)
        cnt[num] -= 1

3. Not Handling Empty Arrays

While the Counter approach naturally handles empty arrays, explicitly checking can prevent unnecessary computation.

Enhancement:

# Early return for edge cases
if not nums1 or not nums2:
    return []