Arrays: Find common element in 3 sorted arrays.

Problem Statement:

Given 3 sorted arrays, you need to find all the common elements in all the 3 elements.

arr1 = 1 3 5 7 9
arr2 = 2 3 6 7 9
arr3 = 1 2 3 4 5 6 7 8 9
Common elements = 3 7 9

This problem can be solved in different ways, we shall solve it with below approaches:

1. By finding intersection of all the arrays

2. Optimized intersection of all the arrays

1. By finding intersection of all the arrays

In this approach, we will first find the intersection of first two arrays. We store the intersection of the two arrays in an temp array.

After that we take the temp array and then check for intersection with the third array

So how do we find the intersection of 2 arrays? We can do it by below steps:

1. We use 2 index i and j that point to the starting of 2 different arrays
2. If arr1[i] is smaller than arr2[j], increment i.
3) If arr1[i] is greater than arr2[j], increment j.
4) If both are same then save the element in temp array and increment both i and j.

The time complexity for this solution is O(n1 + n2 + n3) where n1, n2, n3 are the size of 3 arrays.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

void find_intersection_of_3_arrays(int arr1[], int arr2[], int arr3[], int m, int n, int o) 
{   
    int i = 0;
    int j = 0; 
    int temp_arr[10] = {0};
    int k = 0;

   //find intersection of first 2 arrays
    while (i < m && j < n) 
    { 
        if (arr1[i] < arr2[j]) 
            i++; 
        else if (arr2[j] < arr1[i]) 
            j++; 
        else 
        { 
            temp_arr[k] = arr1[i]; 
            i++; 
            j++; 
            k++;
        } 
    } 
   //find intersection of temp arr and third array
   i = 0;
   j = 0; 

    while (i < k && j < o) 
    { 
        if (temp_arr[i] < arr3[j]) 
            i++; 
        else if (arr3[j] < temp_arr[i]) 
            j++; 
        else 
        { 
            cout<< temp_arr[i] <<" "; 
            i++; 
            j++; 
        } 
    } 

    cout<<endl;

} 
  
int main() 
{ 
    int arr1[] = { 1, 3, 5, 7, 9}; 
    int arr2[] = { 2, 3, 6, 7, 9}; 
    int arr3[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
  
    find_intersection_of_3_arrays(arr1, arr2, arr3, 5, 5, 9 ); 
  
    return 0; 
} 

Output:

3 7 9

2. Optimized intersection of all the arrays

The previous approach uses:

1. Extra space
2. 2 loops

We can further optimize it by using only 1 loop by using below steps:

Let x, y, z be the single element from arr1, arr2, arr3 respectively.

If x, y, and z are same, then print any of them, and increase each array elements by 1

If x < y, then move ahead in A1 as x cannot be a common element

If x > z and y > z, then move ahead for A3, as z cannot be a common element.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

void find_intersection_of_3_arrays(int arr1[], int arr2[], int arr3[], int m, int n, int o) 
{   
  int i = 0;
  int j = 0;
  int k = 0;

   while (i < m && j < n && k < o) 
   {
      if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) 
      {
         cout << arr1[i] << " "; i++; j++; k++;
      }
      else if (arr1[i] < arr2[j])
         i++;
      else if (arr2[j] < arr3[k])
         j++;
      else
         k++;
   }
   cout<<endl;
} 
  
int main() 
{ 
    int arr1[] = { 1, 3, 5, 7, 9}; 
    int arr2[] = { 2, 3, 6, 7, 9}; 
    int arr3[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
  
    find_intersection_of_3_arrays(arr1, arr2, arr3, 5, 5, 9 ); 
  
    return 0; 
} 

Output:

3 7 9