Home » Technical Interview Questions » Array Interview Questions » Find all Common Elements in Given Three Sorted Arrays

Find all Common Elements in Given Three Sorted Arrays


Reading Time - 3 mins

In find all common elements in given three sorted arrays problem, we have given three sorted arrays and you have to find common numbers that is present in all three arrays.

Example

Input:

ar1[] = {1, 5, 10, 20, 40, 80}

ar2[] = {6, 7, 20, 80, 100}

ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output:

20 80

Explanation

Here we have given sorted array and we need to find the common elements in all arrays. We take three-pointers that denote the beginning index of the arrays. Now check the condition that if any element is less than with respect to others then increase that pointer value and not that pointer denotes to the next element. Moving like that till the end where we reach at the end on any array. If we hit the end of an array then stop the iteration and print the result. Now for solid understanding check the below algorithm.

Algorithm for find Common Elements

1. Take three-pointers like variables i, j, and k pointing to the starting index of the three arrays respectively.

2. Check if the three numbers pointed by the variables are same or not

3. If same then print the value and increment all the three variables hence moving forward in the respective arrays.

4. Else increment the variable which is pointing to the smaller ones.

5. If an array gets traversed completely then we check for the remaining two arrays plainly.

READ  Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

6. If two arrays are traversed then simply print the untraversed part of the third array because we know that it is already sorted.

C++ Program for find Common Elements

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int arr1[] = {2, 8, 15 , 20, 35, 45, 100};
  int arr2[] = {5, 9, 20, 45, 110};
      int arr3[] = {3, 4, 15, 20, 30, 45, 80, 120};
      int n1 = sizeof(arr1)/sizeof(arr1[0]);
      int n2 = sizeof(arr2)/sizeof(arr2[0]);
      int n3 = sizeof(arr3)/sizeof(arr3[0]);
  
  
  int  i = 0 ,  j = 0 , k = 0; // i ,j and k are pointing at the  start of 1st , 2nd and 3rd array resepectively.
  
  while(i < n1 and j < n2 and k < n3)
  {
    if(arr1[i] == arr2[j] and arr3[k] == arr1[i]) //if all elements are same then
    {
      cout << arr1[i] <<" ";
      i++; j++; k++;
    }
    //increase the array index variable of those which are small
    else if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr3[k])
      j++;
    else
      k++;
    
  }
  return 0;
}
20 45

Complexity Analysis

Time Complexity – O(max(M, N, P)) where M, N, and P are sizes of the three arrays

Space Complexity – O(1) because here we use some variables only.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions