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,
nums1andnums2.
Outputs:
- An array containing the intersection of
nums1andnums2, 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
-
Hash Table Construction:
- Use a hash table (dictionary) to store the frequency of each element in
nums1.
- Use a hash table (dictionary) to store the frequency of each element in
-
Intersection Finding:
- Iterate through
nums2and 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.
- Iterate through
-
Return Result:
- Return the result list containing the intersection elements.
Complexity Analysis
- Time Complexity: (O(n + m)), where (n) is the length of
nums1and (m) is the length ofnums2. 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
nums1ornums2is 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.