# Find common elements in three sorted arrays

## Find common elements in three sorted arrays

In the Find common elements in three sorted arrays problem, we have to print the elements which are present in all the three arrays given to us. It is a famous interview problem asked in many interviews. In this article, we will provide a C++ solution with an explanation.

## Find the common elements Problem Description

Given three sorted arrays output all elements present in all three arrays.

Input:

• Three arrays of different sizes.

Output:

• Integers present in all three arrays separated by single space.

## Find the common elements Problem Solution

### Brute Force

The idea here is to use three nested loops all loop through all elements. If we arrive same value elements we simply print those.

Time Complexity – O(n1*n2*n3) where n1,n2 & n3 are array sizes.

Space Complexity – O(1)

### Optimized Approach

The idea here is to use sorted nature of the arrays to our advantage. We create three pointers i, j & k . Each of these point to start of an array. We move these pointers according to the following conditions –

• If value of element at i,j & k are equal simple print the element and increment all three pointers.
• If the value is not equal move increment the pointer pointing to the minimum element.
• Repeat above steps till any one pointer reaches the end.

Time Complexity – O(max(n1,n2,n3)) O(n1*n2*n3) where n1,n2 & n3 are array sizes.

Space Complexity – O(1)

### Code

#include <bits/stdc++.h>
using namespace std;
void commonElements(int A[], int B[], int C[], int naint nbint nc)
{
int i = 0j = 0k = 0;

while (i < na && j < nb && k < nc)
{
if (A[i] == B[j] && B[j] == C[k])
{
cout << A[i<< ” “;
i++;
j++;
k++;
}
else
{
if (A[i] <= B[j] && A[i] <= C[k])
i++;
else if (B[j] <= A[i] && B[j] <= C[k])
j++;
else if (C[k] <= A[i] && C[k] <= B[j])
k++;
}
}
}
int main()
{
int A[] = {12358};
int B[] = {1389};
int C[] = {3810};

commonElements(ABC543);
return 0;
}

`3 8`

### 6 comments on “Find common elements in three sorted arrays”

• MD

//Finding common elemments in three arrays

public class Problem1 {
public static void main(String[] args) {
int arr1[]= {1,2,3};
int arr2[]={2,3,4};
int arr3[]={3,4,5};
find(arr1, arr2, arr3);
}

static void find(int[] arr1, int[] arr2, int[] arr3) {
int i = 0;
int j = 0;
int k = 0;
while (i < arr1.length && j < arr2.length && k < arr3.length) {
if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
System.out.println(arr1[i]);
i++;
j++;
k++;
}
else if (arr1[i]<arr2[j]) {
i++;
}
else if(arr2[j]<arr3[k]){
j++;
}
else{
k++;
}
}
}

}

• SWAYAM

Please provide all codes in Python

• Rudransh

a=[1,2,3,5,8,9]
b=[1,3,8,9]
c=[3,8,10,9]
l=[]
for i in a:

if i in b and i in c:
l.append(i)

print(l)