Domain 1EasyCORE

Intersection of Two Arrays II

The problem asks us to find the intersection of two integer arrays, `nums1` and `nums2`. The intersection should include each element as many times as it appears in both arrays. The order of the result does not matter.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Two Pointers#Binary Search#Sort

350. Intersection of Two Arrays II

Model: qwen2.5-coder:14b
Topics: Hash Table,Two Pointers,Binary Search,Sort
FAANG asked: 1
Acceptance rate: 52.1%


Problem Breakdown

The problem asks us to find the intersection of two integer arrays, nums1 and nums2. The intersection should include each element as many times as it appears in both arrays. The order of the result does not matter.

Inputs:

  • Two integer arrays, nums1 and nums2.

Outputs:

  • An array containing the intersection of nums1 and nums2, with elements appearing as many times as they appear in both arrays.

Implicit Constraints or Tricky Edge Cases:

  • The arrays can be empty.
  • Elements can be duplicated.
  • All elements are non-negative integers within the range [0, 1000].

Intuition

A brute-force approach would involve checking each element of nums1 against all elements of nums2, which would result in a time complexity of (O(n \times m)), where (n) and (m) are the lengths of nums1 and nums2, respectively. This is inefficient for large arrays.

A better approach involves using a hash table to count occurrences of each element in one array, then iterating through the other array to find common elements based on these counts. This reduces the time complexity to (O(n + m)).

Approach

  1. Hash Table Construction:

    • Use a hash table (dictionary) to store the frequency of each element in nums1.
  2. Intersection Finding:

    • Iterate through nums2 and for each element, check if it exists in the hash table with a non-zero count.
    • If it does, add the element to the result list and decrement its count in the hash table.
  3. Return Result:

    • Return the result list containing the intersection elements.

Complexity Analysis

  • Time Complexity: (O(n + m)), where (n) is the length of nums1 and (m) is the length of nums2. This is because we iterate through both arrays once.
  • Space Complexity: (O(min(n, m))), for storing the frequency counts in the hash table. The space used is proportional to the smaller array.

Solution

def intersect(nums1, nums2):
    # Step 1: Create a frequency dictionary for nums1
    freq = {}
    for num in nums1:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    
    # Step 2: Find intersection by checking elements in nums2 against the frequency dictionary
    result = []
    for num in nums2:
        if num in freq and freq[num] > 0:
            result.append(num)
            freq[num] -= 1
    
    # Step 3: Return the result list
    return result

Edge Cases Handled

  • Empty Arrays: If either nums1 or nums2 is empty, the function will correctly return an empty list.
  • Duplicated Elements: The solution handles duplicates by maintaining counts in the hash table and decrementing them appropriately.
  • All Unique Elements: If there are no common elements between the two arrays, the result will be an empty list.