Given three integer arrays sorted in ascending order, find the intersection of the three arrays.
Example:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 5, 7, 9]
arr3 = [1, 3, 4, 5, 8]
Expected Output:
[1, 5]
Clarifications:
arr1 = [1, 2, 2, 3]
?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 brute force approach to finding common numbers in three sorted lists involves checking every possible combination of numbers to see if they exist in all three lists. Think of it as comparing each number against every other number to find matches. This method is straightforward but not very efficient for large lists.
Here's how the algorithm would work step-by-step:
def intersection_of_three_sorted_arrays_brute_force(first_array, second_array, third_array):
intersection = []
for number_from_first_array in first_array:
# First, check if current number exists in the second array.
if number_from_first_array in second_array:
# Now, if it exists in the second array, check in the third.
if number_from_first_array in third_array:
# Add it to the result array since it's in all three arrays
intersection.append(number_from_first_array)
return intersection
To find common numbers quickly in three sorted lists, we use a clever method. We move through each list simultaneously, only advancing when a number is smaller than others. This avoids unnecessary checks.
Here's how the algorithm would work step-by-step:
def find_intersection_of_three_arrays(array1, array2, array3):
index_array1 = 0
index_array2 = 0
index_array3 = 0
intersection_result = []
while index_array1 < len(array1) and index_array2 < len(array2) and index_array3 < len(array3):
first_value = array1[index_array1]
second_value = array2[index_array2]
third_value = array3[index_array3]
#If all the values are the same add to the result
if first_value == second_value == third_value:
intersection_result.append(first_value)
index_array1 += 1
index_array2 += 1
index_array3 += 1
else:
# Increment the index of the smallest value
if first_value <= second_value and first_value <= third_value:
index_array1 += 1
#Increment index array 2 if it is the smallest or equal to smallest.
elif second_value <= first_value and second_value <= third_value:
index_array2 += 1
#Otherwise array 3 is the smallest value
else:
index_array3 += 1
return intersection_result
Case | How to Handle |
---|---|
One or more input arrays are null or empty | Return an empty list immediately, as there can be no intersection. |
Arrays of significantly different lengths | The optimal solution should increment the pointer of the array with the smallest current element to minimize unnecessary comparisons. |
All arrays contain the same single element | The intersection should be that single element. |
Arrays contain large numbers that could lead to integer overflow during comparisons or arithmetic operations (if any are used) | Use long or appropriate data types to prevent overflow during calculations, if necessary, or use comparison operators cautiously. |
Arrays contain duplicate values within the same array | The solution should correctly identify intersection elements even with duplicates in input arrays. |
No common elements exist between the three arrays | The solution should return an empty list indicating no intersection. |
Arrays are very large and may cause memory issues if loaded entirely | Iterate through the arrays using pointers or iterators instead of creating large intermediate data structures. |
Arrays contain negative numbers, zeros, or a mix of both | The solution should handle negative numbers and zeros correctly during comparisons and intersection determination. |