Intersection of Three Sorted Arrays

You can find the intersection of three sorted arrays by using pointers for each array and then compare the elements at the current pointers. Here’s the step-by-step guide:

  1. Initialize Pointers: Start with pointers for each array at the beginning (i.e., i = 0, j = 0, k = 0).
  2. Compare Values: Compare the values at the current pointers (i.e., arr1[i], arr2[j], arr3[k]).
  3. Advance Pointers: Based on the comparison, advance the pointers.
  4. Collect Common Elements: If the three values are the same, add them to the result list and advance all three pointers.
  5. Stop Condition: Continue until any of the pointers reaches the end of its corresponding array.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        i, j, k = 0, 0, 0
        result = []

        # Loop until any of the pointers reaches the end of the array
        while i < len(arr1) and j < len(arr2) and k < len(arr3):
            # If all three elements are the same, add to result and move all pointers
            if arr1[i] == arr2[j] == arr3[k]:
                result.append(arr1[i])
                i += 1
                j += 1
                k += 1
            # If arr1's element is the smallest, move its pointer
            elif arr1[i] < arr2[j]:
                i += 1
            # If arr2's element is the smallest, move its pointer
            elif arr2[j] < arr3[k]:
                j += 1
            # If arr3's element is the smallest, move its pointer
            else:
                k += 1

        return result

Explanation:

  • We use three pointers i, j, k to traverse the three arrays.
  • We compare the elements at these pointers and decide which pointers to move forward.
  • If all three elements are the same, we add them to the result and move all pointers forward.

This approach leverages the fact that the arrays are sorted, and hence the time complexity is O(N), where N is the maximum length among the three arrays.