Python - Find Common Elements in Three Sorted Arrays

Python – Find Common Elements in Three Sorted Arrays

This tutorial explains how to find the common elements in three sorted arrays. It is a popular problem in data structures and algorithms (DSA) interviews. We will cover the problem statement, sample inputs and outputs, detailed solution steps, and a complete Python program.

Problem Statement

Given three sorted arrays, the task is to find the elements that are common to all three arrays. The arrays are sorted, which allows us to use an efficient approach with three pointers.

Sample Input and Output

Example 1:

</>

Copy

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

# Expected Output: [20, 80]

Example 2:

</>

Copy

# Input arrays
arr1 = [2, 4, 6, 8]
arr2 = [4, 8, 12, 16]
arr3 = [0, 4, 8, 20]

# Expected Output: [4, 8]

Solution Approach

We can efficiently find the common elements using a three-pointer technique. Here are the steps:

Initialize three pointers i, j, and k to 0, one for each array.
While none of the pointers have reached the end of their respective arrays:
1. If arr1[i], arr2[j], and arr3[k] are equal, add the element to the result list and increment all three pointers.
2. If they are not equal, increment the pointer that is at the smallest element, because the arrays are sorted.
Repeat until at least one array is fully traversed.

This approach has a time complexity of O(n1 + n2 + n3), where n1, n2, and n3 are the sizes of the three arrays, making it efficient for large inputs.

Python Program

</>

Copy

def find_common_elements(arr1, arr2, arr3):
    # Initialize pointers for all three arrays
    i = j = k = 0
    common = []
    
    # Traverse all arrays simultaneously
    while i < len(arr1) and j < len(arr2) and k < len(arr3):
        # If elements at current pointers are equal, it's a common element
        if arr1[i] == arr2[j] == arr3[k]:
            common.append(arr1[i])
            i += 1
            j += 1
            k += 1
        # Move the pointer that points to the smallest element
        elif arr1[i] < arr2[j]:
            i += 1
        elif arr2[j] < arr3[k]:
            j += 1
        else:
            k += 1
    return common

# Example 1
arr1 = [1, 5, 10, 20, 40, 80]
arr2 = [6, 7, 20, 80, 100]
arr3 = [3, 4, 15, 20, 30, 70, 80, 120]
print("Common Elements (Example 1):", find_common_elements(arr1, arr2, arr3))

# Example 2
arr1 = [2, 4, 6, 8]
arr2 = [4, 8, 12, 16]
arr3 = [0, 4, 8, 20]
print("Common Elements (Example 2):", find_common_elements(arr1, arr2, arr3))

Conclusion

In this tutorial, we learned how to find common elements in three sorted arrays using the three-pointer approach. This method efficiently traverses the arrays and finds common elements with a time complexity of O(n1 + n2 + n3).

TutorialKart

Python – Find Common Elements in Three Sorted Arrays