Three-Pointer Algorithm for Finding Common Element

The three-pointer technique is used to find common elements in three sorted arrays efficiently. It minimizes time complexity while keeping space usage low.

Step 1: Initialize Pointers

Start by setting three pointers: i, j, and k to the beginning of arr1, arr2, and arr3 respectively.

Step 2: Compare Elements

Check if the elements at the current pointers are equal:

• If arr1[i] == arr2[j] == arr3[k], then we have found a common element. Add it to the result list and move all pointers forward.
• If the elements are not equal, move the pointer pointing to the smallest element forward.

Step 3: Move the Pointer of the Smallest Element

This step ensures we do not skip any potential common elements:

• If arr1[i] < arr2[j], move i forward.
• If arr2[j] < arr3[k], move j forward.
• Otherwise, move k forward.

Step 4: Repeat Until End of Arrays

Continue this process until one of the pointers reaches the end of its array. The result list will contain all common elements found.

Example

Consider the following arrays:

arr1 = [1, 5, 10, 20, 40, 80]
arr2 = [6, 7, 20, 80, 100]
arr3 = [3, 4, 15, 20, 30, 70, 80, 120]
        

Output: [20, 80]

Why This Algorithm Works

By moving the pointer of the smallest element, we ensure that we do not skip any potential common elements. This approach takes advantage of the sorted order of the arrays and efficiently reduces the search space.

Python3 Code

class Solution:
    def commonElements(self, arr1, arr2, arr3):
        i = j = k = 0
        result = []
        
        while i < len(arr1) and j < len(arr2) and k < len(arr3):
            # If all elements are equal, add to the result
            if arr1[i] == arr2[j] == arr3[k]:
                result.append(arr1[i])
                i += 1
                j += 1
                k += 1
            # Move the pointer of the smallest element
            elif arr1[i] < arr2[j]:
                i += 1
            elif arr2[j] < arr3[k]:
                j += 1
            else:
                k += 1
        
        return result
    

Visualization