Given two integer arrays nums1
and nums2
, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays, and you may return the result in any order.
For example:
nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]
As another example:
nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9]
or [9, 4]
Can you implement a function to find the intersection of two arrays, handling duplicate elements correctly, and optimizing for time and space complexity?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The core idea is to compare each number from the first list with every number in the second list to find matches. We keep track of the matches we find, which represent numbers present in both lists.
Here's how the algorithm would work step-by-step:
def intersection_of_two_arrays_ii_brute_force(first_array, second_array):
intersection_result = []
for first_array_index in range(len(first_array)):
first_array_element = first_array[first_array_index]
second_array_index = 0
while second_array_index < len(second_array):
second_array_element = second_array[second_array_index]
# Check for common element across arrays
if first_array_element == second_array_element:
intersection_result.append(first_array_element)
del second_array[second_array_index]
# Exit current search after match
break
else:
second_array_index += 1
return intersection_result
The efficient approach leverages sorting and comparison to find common elements. We first arrange the elements within each collection, and then use a strategy of advancing through each collection based on element comparison to identify and count common elements effectively.
Here's how the algorithm would work step-by-step:
def intersection_of_two_arrays_ii(first_array, second_array):
first_array.sort()
second_array.sort()
index_first_array = 0
index_second_array = 0
result = []
while index_first_array < len(first_array) and index_second_array < len(second_array):
# If elements are equal, add to result and advance both
if first_array[index_first_array] == second_array[index_second_array]:
result.append(first_array[index_first_array])
index_first_array += 1
index_second_array += 1
# Increment the first array if its value is smaller
elif first_array[index_first_array] < second_array[index_second_array]:
index_first_array += 1
# Increment the second array if its value is smaller
else:
index_second_array += 1
return result
Case | How to Handle |
---|---|
One or both input arrays are null or empty. | Return an empty list if either input array is null or has zero length. |
One array is significantly larger than the other. | Use a hash map approach with the smaller array to improve efficiency in lookup. |
Both arrays contain all the same numbers. | The algorithm should correctly count and intersect the occurrences of each number. |
Arrays contain very large numbers (close to integer limits). | The solution should handle large numbers without integer overflow issues. |
Arrays contain duplicate numbers. | The hash map approach naturally handles duplicates by counting their occurrences. |
No common elements exist between the two arrays. | The algorithm should return an empty list in this case. |
Arrays contain negative numbers and zero. | The hash map approach works correctly with negative numbers and zero as keys. |
Arrays are extremely large, potentially exceeding available memory. | Consider a divide-and-conquer approach or external memory algorithms for extremely large datasets. |