Common Elements in Three Sorted Arrays in C

Finding common elements in multiple arrays is a common problem in programming and interviews.

When arrays are sorted, we can solve this efficiently using a pointer-based approach instead of nested loops.

In this tutorial, we will find common elements in three sorted arrays using C.

Concept Overview

We use three pointers to traverse the arrays simultaneously.

At each step, we compare elements and move the pointer of the smallest value.

This avoids unnecessary comparisons and improves efficiency.

Problem Statement

Given three sorted arrays, find all elements that are common in all three arrays.

Example

Input:
Array1: 1 5 10 20 40 80
Array2: 6 7 20 80 100
Array3: 3 4 15 20 30 70 80

Output:
20 80

Approach

1. Initialize three pointers i, j, k to 0.

2. Compare elements of all three arrays.

3. If all are equal, print the element and move all pointers.

4. Otherwise, move the pointer of the smallest element.

5. Repeat until any array ends.

C Program

#include <stdio.h>

void findCommon(int arr1[], int arr2[], int arr3[], int n1, int n2, int n3) {
    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2 && k < n3) {
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            printf("%d ", arr1[i]);
            i++;
            j++;
            k++;
        }
        else if (arr1[i] < arr2[j]) {
            i++;
        }
        else if (arr2[j] < arr3[k]) {
            j++;
        }
        else {
            k++;
        }
    }
}

int main() {
    int arr1[] = {1, 5, 10, 20, 40, 80};
    int arr2[] = {6, 7, 20, 80, 100};
    int arr3[] = {3, 4, 15, 20, 30, 70, 80};

    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    int n3 = sizeof(arr3)/sizeof(arr3[0]);

    printf("Common elements are: ");
    findCommon(arr1, arr2, arr3, n1, n2, n3);

    return 0;
}

Output

Common elements are: 20 80

Detailed Explanation

The program uses three pointers to iterate through the arrays.

When elements match, they are printed as common.

If elements differ, the pointer of the smallest value moves forward.

This ensures efficient traversal without redundant checks.

Time and Space Complexity

Time Complexity: O(n1 + n2 + n3)

Space Complexity: O(1)

Applications

Used in data analysis and merging datasets.

Helpful in search systems and database queries.

Advantages

Efficient compared to brute force methods.

Simple and easy to implement.

Limitations

Works only with sorted arrays.

Does not handle duplicate filtering automatically.

Improvements You Can Make

Modify the program to remove duplicates.

Extend logic for more than three arrays.

Use dynamic memory for variable input sizes.

Mastering this approach helps you solve many array intersection problems efficiently.