We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Intersection of Three Sorted Arrays

Number: 1149

Difficulty: Easy

Paid? Yes

Companies: Meta

Problem Description

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Key Insights

  • Since all arrays are sorted in strictly increasing order, we can efficiently use three pointers.
  • By comparing the current elements pointed to in each array, determine if the element is common.
  • Advance the pointer(s) corresponding to the smallest element when elements differ.
  • The approach avoids extra space for hash structures and does a linear scan through the arrays.

Space and Time Complexity

Time Complexity: O(n1 + n2 + n3), where n1, n2, n3 are the lengths of arr1, arr2, and arr3 respectively. Space Complexity: O(1) extra space (excluding the output array).

Solution

We use three pointers (one for each array) to traverse the arrays concurrently:

  1. If the elements at all three pointers are equal, add that element to the result list and move all three pointers forward.
  2. If they are not equal, move the pointer that points to the smallest element.
  3. Continue until one of the arrays is completely traversed.
    This technique leverages the sorted property of the arrays to ensure that no element is missed and maintains a linear time complexity.

Code Solutions

# Function to compute intersection of three sorted arrays
def intersection(arr1, arr2, arr3):
    # Initialize pointers for each array
    i, j, k = 0, 0, 0
    common_elements = []
    
    # Traverse all arrays while pointers are within their boundaries
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        # If current elements are equal, it is common to all arrays
        if arr1[i] == arr2[j] == arr3[k]:
            common_elements.append(arr1[i])
            i += 1
            j += 1
            k += 1
        # Move pointer in the array with the smallest element
        elif arr1[i] < arr2[j]:
            i += 1
        elif arr2[j] < arr3[k]:
            j += 1
        else:
            k += 1
            
    return common_elements

# Example usage
print(intersection([1,2,3,4,5], [1,2,5,7,9], [1,3,4,5,8]))
← Back to All Questions