Find all common elements in given three sorted arrays

We have three sorted arrays and you have to find common numbers which is present in all three arrays

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

ALGORITHM

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

SPACE COMPLEXITY – O(1)

1. Take three pointer 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.

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

#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;
}
Try It




Next > < Prev
Scroll to Top