- Write a program to find common elements of three sorted array.
- Linear time algorithm to find common elements of three sorted array.

Given three sorted array of size N1, N2 and N3. we have to **find common elements of three sorted array**.

For Example :

Input Array One = 1 5 10 15 20 25 30 Input Array Two = 3 4 5 10 15 25 30 38 Input Array Three = 0 2 5 13 15 16 17 25 32 Output : Common Elements : 5 15 25

Let arrayOne, arrayTwo and arrayThree be three sorted array of size N1, N2 and N3.

**Brute Force Method**

- Using three for loop, generate all possible combination of triplet(one from each input array) and check if they are equal.
- This approach is not using the fact that input arrays are sorted.

^{3})

**By finding intersection of input arrays**

We can reduce the time complexity by using the fact that input arrays are sorted. There are two steps in this algorithm:

In worst case this algorithm used a temporary array of size which is equal to Minimum of (N1, N2, N3).

- Find the common elements of arrayOne and arrayTwo and store it in a temporary array tempArray.
- Now, find the common element of tempArray and arrayOne.

- Initialize indexOne and indexTwo to the index of smallest element of arrayOne and arrayTwo respectively.(indexOne = indexTwo = 0;)
- If arrayOne[indexOne] == arrayTwo[indexTwo], we found a common element. Store it in a temporary array and increment both indexOne and indexTwo.
- If arrayOne[indexOne] < arrayTwo[indexTwo], then increment indexOne otherwise increment indexTwo.
- Continue until we reached end of any one array.

In worst case this algorithm used a temporary array of size which is equal to Minimum of (N1, N2, N3).

**By finding intersection of all three input arrays at a time**

Above algorithm uses a temporary array and finds intersection of two arrays twice. We can further improve it by finding intersection of all three input array using a single loop.This algorithm is extension of above mentioned algorithm to find intersection of two arrays.

- Initialize indexOne, indexTwo and indexThree to the index of smallest element of arrayOne, arrayTwo and arrayThree respectively.(indexOne = indexTwo = indexThree = 0;)
- If arrayOne[indexOne] == arrayTwo[indexTwo] == arrayThree[indexThree], we found a common element. Print it and increment all three indexes.
- Else increment the index of smallest of arrayOne[indexOne], arrayTwo[indexTwo] and arrayThree[indexThree]
- Continue until we reached end of any one array.

## C program to find common elements of three sorted array

#include <stdio.h> /* Prints common elements of three sorted array */ void printCommonElements(int *array1, int *array2, int *array3, int s1, int s2, int s3) { int i, j, k; /* Initialize i, j and k to point to the smallest element of array1, array2, and array3 respectively */ i = j = k = 0; /* Iterate until any one array ends */ while (i < s1 && j < s2 && k < s3) { /* Compare current element of all three arrays */ if(array1[i] == array2[j] && array2[j] == array3[k]) { /* found one common element */ printf("%d ", array1[i]); /* Increment all three pointers */ i++; j++; k++; } else if ((array1[i] <= array2[j]) && (array1[i] <= array3[k])){ /* array1[i] is smallest, increment i*/ i++; } else if ((array2[j] <= array3[k]) && (array2[j] <= array1[i])){ /* array2[j] is smallest, increment j*/ j++; } else { /* array3[k] is smallest, increment k*/ k++; } } } int main() { int array1[7] = {1, 5, 10, 15, 20, 25, 30}; int array2[8] = {3, 4, 5, 10, 15, 25, 30, 38}; int array3[9] = {0, 2, 5, 13, 15, 16, 17, 25, 32}; printCommonElements(array1, array2, array3, 7, 8, 9); return 0; }Output

5 15 25