Taro Logo

Intersection of Three Sorted Arrays

Easy
Meta logo
Meta
2 views
Topics:
ArraysTwo Pointers

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:

  • Can the arrays be empty? If so, what should be returned?
  • What should be returned if there is no intersection?
  • Are the arrays guaranteed to be sorted? If not, should I sort them first?
  • How should duplicate values within a single array be handled (e.g., arr1 = [1, 2, 2, 3]?
  • What is the expected time and space complexity?
  • Can you provide a test case with larger arrays to evaluate the solution's performance?

Solution


Clarifying Questions

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:

  1. Can the input arrays be empty or null?
  2. What is the range of integer values within the arrays? Should I be concerned about integer overflow?
  3. Are duplicates allowed within each individual array? If so, should the intersection also include duplicates reflecting their frequency in all three arrays, or just the unique intersecting values?
  4. If there is no intersection, should I return an empty list or null?
  5. Are the arrays guaranteed to be sorted in strictly ascending order (no duplicates next to each other), or just non-decreasing order?

Brute Force Solution

Approach

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:

  1. Take the first number from the first list.
  2. Check if this number is also present in the second list.
  3. If it is present in the second list, then check if it is also present in the third list.
  4. If the number is present in all three lists, then it's part of the intersection, so keep track of it.
  5. Move to the next number in the first list and repeat steps 2-4.
  6. Continue doing this until you've gone through all the numbers in the first list.
  7. The numbers you kept track of are the intersection of the three sorted lists.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n*m*p)The provided brute force approach iterates through each element of the first array (let's say it has n elements). For each of these n elements, it searches in the second array (let's say it has m elements), and if found, it searches in the third array (let's say it has p elements). In the worst case, for each of the n elements in the first array, we might have to iterate through all m elements in the second array and then all p elements in the third array. Therefore, the total number of operations can be approximated as n * m * p, leading to a time complexity of O(n*m*p).
Space Complexity
O(N)The brute force approach requires keeping track of the intersection elements. The plain English description mentions 'keeping track of it', implying an auxiliary data structure, such as a list, to store the common numbers found. In the worst-case scenario, all elements of the first list could be present in all three lists, resulting in a list of size N, where N is the number of elements in the first list. Therefore, the space complexity is O(N).

Optimal Solution

Approach

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:

  1. Start by looking at the beginning of each of the three lists.
  2. Compare the first number in each list.
  3. If all three numbers are the same, then this number is in all three lists; record this number.
  4. If the numbers are not all the same, find the smallest number among the three.
  5. Advance to the next number in the list that contained the smallest number. The goal is to catch up to the other lists.
  6. Repeat the comparison process (steps 2-5) until you reach the end of any of the lists.
  7. The numbers you recorded are the numbers that appear in all three lists.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the three arrays, advancing the pointer of the array with the smallest current element. In the worst-case scenario, each element in all three arrays is visited once. Since the arrays are traversed linearly, the total number of operations is proportional to the sum of the lengths of the arrays. If we assume the maximum length among the three arrays is 'n', then in the worst case each array is of length 'n', resulting in approximately 3n operations. Therefore, the time complexity is O(n).
Space Complexity
O(N)The algorithm identifies and records common numbers between the three sorted arrays. These common numbers are stored in a separate data structure, most likely a list or array. In the worst-case scenario, all elements in the shortest array are present in the other two, meaning the output array could potentially hold a number of elements proportional to the size of the smallest input array, which we can denote as N. Therefore, the auxiliary space needed to store the intersection is O(N).

Edge Cases

CaseHow to Handle
One or more input arrays are null or emptyReturn an empty list immediately, as there can be no intersection.
Arrays of significantly different lengthsThe optimal solution should increment the pointer of the array with the smallest current element to minimize unnecessary comparisons.
All arrays contain the same single elementThe 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 arrayThe solution should correctly identify intersection elements even with duplicates in input arrays.
No common elements exist between the three arraysThe solution should return an empty list indicating no intersection.
Arrays are very large and may cause memory issues if loaded entirelyIterate through the arrays using pointers or iterators instead of creating large intermediate data structures.
Arrays contain negative numbers, zeros, or a mix of bothThe solution should handle negative numbers and zeros correctly during comparisons and intersection determination.