Domain 1EasyCORE

Intersection of Three Sorted Arrays

The problem requires finding the intersection of three sorted arrays. The inputs are three integer arrays `arr1`, `arr2`, and `arr3`, each sorted in strictly increasing order. The output should be a sorted array containing only the integers that appear in all three input arrays.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Two Pointers

1213. Intersection of Three Sorted Arrays

Model: qwen2.5-coder:14b
Topics: Hash Table,Two Pointers
FAANG asked: 1
Acceptance rate: 79.4%


Problem Breakdown

The problem requires finding the intersection of three sorted arrays. The inputs are three integer arrays arr1, arr2, and arr3, each sorted in strictly increasing order. The output should be a sorted array containing only the integers that appear in all three input arrays.

Inputs:

  • Three sorted integer arrays: arr1, arr2, and arr3.

Outputs:

  • A sorted array of integers that are common to all three input arrays.

Implicit Constraints/Edge Cases:

  • The arrays can be empty.
  • The arrays may contain duplicate elements, but since they are strictly increasing, duplicates will not occur within each array.
  • The range of values in the arrays is between 1 and 2000.

Intuition

A brute-force approach would involve checking every element in arr1 to see if it exists in both arr2 and arr3. This approach would have a time complexity of O(n^2), where n is the length of the longest array, which is inefficient given the constraints.

The key insight is that since the arrays are sorted, we can use a two-pointer technique to efficiently find common elements. By maintaining pointers for each array and moving them in unison based on their values, we can reduce the time complexity significantly.

Approach

  1. Initialize three pointers i, j, and k to 0, one for each array.
  2. Traverse all arrays simultaneously:
    • If the elements at the current pointers are equal, add the element to the result list and move all three pointers forward.
    • If the elements are not equal, increment the pointer of the array with the smallest element to try and catch up with the others.
  3. Continue this process until one of the arrays is fully traversed.
  4. Return the result list.

This approach leverages the sorted nature of the arrays and ensures that we only traverse each array once, achieving a linear time complexity relative to the total number of elements across all arrays.

Complexity Analysis

  • Time Complexity: O(n), where n is the sum of the lengths of arr1, arr2, and arr3. We traverse each element at most once.
  • Space Complexity: O(1) for the pointers, plus O(min(m, p, q)) for the result list, where m, p, and q are the lengths of arr1, arr2, and arr3, respectively.

Solution

def arraysIntersection(arr1, arr2, arr3):
    i, j, k = 0, 0, 0
    result = []
    
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        if arr1[i] == arr2[j] == arr3[k]:
            result.append(arr1[i])
            i += 1
            j += 1
            k += 1
        elif arr1[i] <= arr2[j]:
            i += 1
        elif arr2[j] <= arr3[k]:
            j += 1
        else:
            k += 1
    
    return result

Edge Cases Handled

  • Empty Arrays: If any of the arrays are empty, the function will immediately return an empty list since the while loop condition will fail.
  • No Common Elements: If there are no common elements among the three arrays, the function will traverse all arrays without adding anything to the result list and return an empty list.
  • All Elements Common: If all elements in the arrays are common, they will be added to the result list as we move through the arrays.