Given two integer arrays nums1
and nums2
, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
For example:
nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
(or [4,9]
)
Write a function to find the intersection of two integer arrays, ensuring that the elements in the result are unique and can be returned in any order. Consider the cases where the input arrays might be empty or contain duplicate elements. Discuss the time and space complexity of your solution. Can you think of multiple approaches and what the trade offs are?
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:
To find common numbers between two lists, the brute force way is like comparing each number from the first list with every number in the second list. We continue this process until we've checked all possible pairs of numbers from both lists.
Here's how the algorithm would work step-by-step:
def intersection_of_two_arrays_brute_force(first_array, second_array):
intersection_result = []
for first_array_element in first_array:
# Iterate through the second array to find matches for current element.
for second_array_element in second_array:
if first_array_element == second_array_element:
# Ensure we only add distinct elements to the intersection.
if first_array_element not in intersection_result:
intersection_result.append(first_array_element)
return intersection_result
The most efficient way to find common elements between two collections is to use a way of organizing one collection that allows for very quick lookups. We can then iterate through the second collection and quickly check if each element exists in the first collection's special organization. This avoids comparing each element in one collection to every element in the other collection.
Here's how the algorithm would work step-by-step:
def intersection_of_two_arrays(first_array, second_array):
first_array_set = set()
for element in first_array:
first_array_set.add(element)
intersection_result = []
# Use the set for quick lookups.
for element in second_array:
if element in first_array_set:
intersection_result.append(element)
# Remove the element to avoid duplicates
first_array_set.remove(element)
return intersection_result
def intersection_of_two_arrays_alt(first_array, second_array):
# Use a set for quick lookups of elements in first_array
first_array_set = set(first_array)
intersection_result = []
# Iterate through the second array and check for presence in the set.
for element in second_array:
if element in first_array_set:
intersection_result.append(element)
first_array_set.discard(element)
return intersection_result
def intersection_of_two_arrays_optimized(first_array, second_array):
# Convert the first array to a set for O(1) lookups
first_array_set = set(first_array)
intersection_result = []
# Iterate through the second array
for element in second_array:
# Only add to result if element is in the first array set.
if element in first_array_set:
intersection_result.append(element)
# To avoid duplicates, remove the element from the set
first_array_set.remove(element)
return intersection_result
Case | How to Handle |
---|---|
One or both input arrays are null or empty | Return an empty array if either nums1 or nums2 is null or empty. |
One array is significantly larger than the other | Use the smaller array to build the frequency map to optimize memory usage. |
Both arrays contain only one element | Compare the single elements and return the array containing the element if they are equal or an empty array otherwise. |
Arrays contain large positive or negative integers near the integer limits | The chosen solution (hash map/dictionary approach) should handle large integer values without causing overflow unless integer limits are exceeded during element counting; consider using 64 bit integers if necessary. |
Arrays contain duplicate elements with differing frequencies | Use a hash map (or similar) to count element occurrences, and decrement the counts during intersection to ensure the correct frequency of intersection elements. |
No intersection exists between the two arrays | The algorithm should return an empty array when no common elements are found. |
All elements in both arrays are the same | The result should contain the element repeated the number of times it appears in the shorter array. |
Input arrays are extremely large and do not fit into memory | Consider using an external sort approach where the arrays are sorted on disk, and then a merge-like algorithm is used to find the intersection using chunks of data. |