Intersection of Three Sorted Arrays

Intersection of Three Sorted Arrays

1. What is this problem about?

The Intersection of Three Sorted Arrays interview question asks you to find all the numbers that are present in three different arrays. Crucially, all three input arrays are already sorted in strictly increasing order.

2. Why is this asked in interviews?

Companies like Apple and Meta use this to test your ability to leverage the Sorted property. While a Hash Map approach ($O(N)$ space) is valid, the interviewer is usually looking for the $O(1)$ space Two Pointers (or in this case, Three Pointers) approach. It tests your proficiency with Array interview patterns.

3. Algorithmic pattern used

This problem uses the Multiple Pointers pattern.

1. Three Pointers: Initialize p1 = 0, p2 = 0, p3 = 0.
2. Compare:
   • If arr1[p1] == arr2[p2] == arr3[p3], you found a common element. Add it to result and increment all three pointers.
   • Otherwise, you need to "catch up." Increment the pointer pointing to the smallest of the three values.
3. Termination: Stop when any pointer reaches the end of its array.

4. Example explanation

A = [1, 2, 5], B = [2, 3, 5], C = [2, 5, 8]

1. p1=0(1), p2=0(2), p3=0(2). A is smallest. p1++.
2. p1=1(2), p2=0(2), p3=0(2). All equal! Add 2. p1++, p2++, p3++.
3. p1=2(5), p2=1(3), p3=1(5). B is smallest. p2++.
4. p1=2(5), p2=2(5), p3=1(5). All equal! Add 5. Result: [2, 5].

5. Common mistakes candidates make

• Inefficient Search: Using binary search for every element of the first array in the other two. This is $O(N \log M)$, which is slower than the $O(N)$ three-pointer pass.
• Extra Space: Using a Hash Map when the "sorted" constraint allows for a constant space solution.
• Handling Duplicates: Forgetting that if the arrays could have duplicates, you need to handle pointer increments carefully (though the problem usually guarantees strictly increasing).

6. Interview preparation tip

Always look for "Two Pointers" when multiple arrays are sorted. Moving pointers based on relative magnitude is a fundamental Sorting interview pattern that avoids $O(N^2)$ comparisons.