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 na, int nb, int nc)
{
int i = 0, j = 0, k = 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[] = {1, 2, 3, 5, 8};
int B[] = {1, 3, 8, 9};
int C[] = {3, 8, 10};
commonElements(A, B, C, 5, 4, 3);
return 0;
}Output
3 8
Login/Signup to comment
//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++;
}
}
}
}
Please provide all codes in Python
Hey, surely we will forward your message to our team ☺
ok
import java.util.*;
public class Sample
{
public static void main(String arg[])
{
ArrayList al=new ArrayList();
int a[]={1,2,3,4,5};
int b[]={5,2,6,7,1,9};
int c[]={0,5,2,7,1,4,2,8,67};
Arrays.sort(b);
Arrays.sort(c);
for(int i=0;i=0 && Arrays.binarySearch(c,a[i])>=0)
{
al.add(a[i]);
}
}
System.out.println(al+”\n”);
for(Integer ele:al)
{
System.out.print(ele+” “);
}
}
}
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)