349. Intersection of Two Arrays
Model: qwen2.5-coder:14b
Topics: Hash Table,Two Pointers,Binary Search,Sort
FAANG asked: 1
Acceptance rate: 65.3%
Problem Breakdown
The problem asks us to find the intersection of two integer arrays, nums1 and nums2. The intersection should contain only unique elements, and the order of the result does not matter. The constraints are that both arrays can have a length between 1 and 1000, and each element in the arrays is between 0 and 1000.
Key points:
- Inputs: Two integer arrays
nums1andnums2. - Output: An array containing unique elements that are present in both input arrays.
- Constraints: The result should not contain duplicates, and the order of elements in the output does not matter.
- Edge Cases:
- Either or both arrays could be empty.
- Arrays could have duplicate elements.
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 * m), where n and m are the lengths of nums1 and nums2, respectively. This is inefficient given the constraints.
The key insight to improve this is to use a data structure that allows for fast lookups, such as a hash set. By storing one array in a set, we can then iterate through the other array and check for membership in the set, which is an O(1) operation on average. This reduces the time complexity to O(n + m).
Approach
- Convert one of the arrays to a set: This allows for O(1) average-time complexity lookups.
- Iterate through the other array: For each element, check if it exists in the set.
- Store unique elements: Use another set to store the intersection elements to ensure uniqueness.
- Return the result as a list: Convert the set of intersection elements back to a list.
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 each array once. - Space Complexity: O(min(n, m)), due to the storage used by the set. In the worst case, this could be the size of one of the arrays.
Solution
def intersection(nums1, nums2):
# Convert nums1 to a set for fast lookups
set1 = set(nums1)
# Use another set to store unique intersection elements
intersection_set = set()
# Iterate through nums2 and check for membership in set1
for num in nums2:
if num in set1:
intersection_set.add(num)
# Convert the set of intersection elements back to a list
return list(intersection_set)
# Example usage:
# print(intersection([1, 2, 2, 1], [2, 2])) # Output: [2]
# print(intersection([4, 9, 5], [9, 4, 9, 8, 4])) # Output: [9, 4]
Edge Cases Handled
- Empty Arrays: If either or both arrays are empty, the result will be an empty list.
- Duplicate Elements: The use of sets ensures that only unique elements are included in the intersection.