Program to Find Common Elements of Three Sorted Array

  • 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.
Time Complexity : O(n3)
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:
  1. Find the common elements of arrayOne and arrayTwo and store it in a temporary array tempArray.
  2. Now, find the common element of tempArray and arrayOne.
Here is the algorithm to find common elements of two sorted array. This algorithm is similar to merge step of merge sort. Let's say we want to find common elements of arrayOne and arrayTwo.
  • 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.
Time Complexity : O(N1 + N2 + N3)
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.
Time Complexity : O(N1 + N2 + N3)

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
Posted by
Labels: ,