Find common elements in three sorted arrays
Last Updated :
02 Oct, 2023
Given three Sorted arrays in non-decreasing order, print all common elements in these arrays.
Examples:
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
Input:
ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
Common elements in three sorted arrays using two pointer:
A simple solution is to first find the intersection of two arrays and store the intersection in a temporary array, then find the intersection of the third array and temporary array.
- Initialize both pointers i and j to 0, and an empty list common.
- While both pointers i and j are within the bounds of the two arrays:
- If arr1[i] is less than arr2[j], increment i by 1.
- If arr2[j] is less than arr1[i], increment j by 1.
- If arr1[i] is equal to arr2[j]:
- Add arr1[i] to the common list.
- Increment both i and j by 1.
- Return the common list containing the common elements of the two arrays.
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
void FindIntersection(int arr1[], int arr2[], int temp[],
int m, int n, int& k)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr2[j] < arr1[i]) {
j++;
}
else {
temp[k] = arr1[i];
i++;
j++;
k++;
}
}
}
int main()
{
int arr1[] = { 1, 5, 10, 20, 40, 80 };
int arr2[] = { 6, 7, 20, 80, 100 };
int arr3[] = { 3, 4, 15, 20, 30, 70, 80, 120 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int n3 = sizeof(arr3) / sizeof(arr3[0]);
int temp[200000];
int ans[200000];
int k = 0;
FindIntersection(arr1, arr2, temp, n1, n2, k);
int tempSize = k;
k = 0;
FindIntersection(arr3, temp, ans, n3, tempSize, k);
cout << "Common elements present in arrays are : \n";
for (int i = 0; i < k; i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
|
Java
import java.io.*;
public class GFG {
static void findIntersection(int[] arr1, int[] arr2,
int[] temp, int m, int n,
int[] k)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr2[j] < arr1[i]) {
j++;
}
else {
temp[k[0]] = arr1[i];
i++;
j++;
k[0]++;
}
}
}
public static void main(String[] args)
{
int[] arr1 = { 1, 5, 10, 20, 40, 80 };
int[] arr2 = { 6, 7, 20, 80, 100 };
int[] arr3 = { 3, 4, 15, 20, 30, 70, 80, 120 };
int n1 = arr1.length;
int n2 = arr2.length;
int n3 = arr3.length;
int[] temp = new int[200000];
int[] ans = new int[200000];
int[] k = {
0
};
findIntersection(arr1, arr2, temp, n1, n2, k);
int tempSize = k[0];
k[0] = 0;
findIntersection(arr3, temp, ans, n3, tempSize, k);
System.out.println(
"Common elements present in arrays are :");
for (int i = 0; i < k[0]; i++) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
}
|
Python3
def find_intersection(arr1, arr2, temp, m, n, k):
i = 0
j = 0
while i < m and j < n:
if arr1[i] < arr2[j]:
i += 1
elif arr2[j] < arr1[i]:
j += 1
else:
temp[k[0]] = arr1[i]
i += 1
j += 1
k[0] += 1
def main():
arr1 = [1, 5, 10, 20, 40, 80]
arr2 = [6, 7, 20, 80, 100]
arr3 = [3, 4, 15, 20, 30, 70, 80, 120]
n1 = len(arr1)
n2 = len(arr2)
n3 = len(arr3)
temp = [0] * 200000
ans = [0] * 200000
k = [0]
find_intersection(arr1, arr2, temp, n1, n2, k)
temp_size = k[0]
k[0] = 0
find_intersection(arr3, temp, ans, n3, temp_size, k)
print("Common elements present in arrays are:")
for i in range(k[0]):
print(ans[i], end=" ")
print()
if __name__ == "__main__":
main()
|
C#
using System;
public class GFG {
static void FindIntersection(int[] arr1, int[] arr2,
int[] temp, int m, int n,
int[] k)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr2[j] < arr1[i]) {
j++;
}
else {
temp[k[0]] = arr1[i];
i++;
j++;
k[0]++;
}
}
}
public static void Main(string[] args)
{
int[] arr1 = { 1, 5, 10, 20, 40, 80 };
int[] arr2 = { 6, 7, 20, 80, 100 };
int[] arr3 = { 3, 4, 15, 20, 30, 70, 80, 120 };
int n1 = arr1.Length;
int n2 = arr2.Length;
int n3 = arr3.Length;
int[] temp = new int[200000];
int[] ans = new int[200000];
int[] k = {
0
};
FindIntersection(arr1, arr2, temp, n1, n2, k);
int tempSize = k[0];
k[0] = 0;
FindIntersection(arr3, temp, ans, n3, tempSize, k);
Console.WriteLine(
"Common elements present in arrays are :");
for (int i = 0; i < k[0]; i++) {
Console.Write(ans[i] + " ");
}
Console.WriteLine();
}
}
|
Javascript
function findIntersection(arr1, arr2) {
let i = 0;
let j = 0;
const temp = [];
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
i++;
} else if (arr2[j] < arr1[i]) {
j++;
} else {
temp.push(arr1[i]);
i++;
j++;
}
}
return temp;
}
function main() {
const arr1 = [1, 5, 10, 20, 40, 80];
const arr2 = [6, 7, 20, 80, 100];
const arr3 = [3, 4, 15, 20, 30, 70, 80, 120];
const temp = findIntersection(arr1, arr2);
const ans = findIntersection(temp, arr3);
console.log("Common elements present in arrays are:");
for (const element of ans) {
console.log(element);
}
}
main();
|
Output
Common elements present in arrays are :
20 80
Time complexity: O(n1 + n2 + n3), where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.
Auxiliary Space: O(max(n1,n2,n3))
Common elements in three sorted arrays using three pointer:
It is known that the arrays are sorted in a non-decreasing order. When a common integer has been found, we want to move forward in each array in search of another common integer. Otherwise, the smaller integer among the three must not be common.
The reason for this is that at least one of the other integers is a larger integer, and as we move forward in the array, we only encounter larger integers. In this case, we want to proceed with only the array that contains the smaller integer.
- Create and initialize three variables i, j, and k with 0, it will point to the indices of the arrays.
- Repeat the following steps until we reach the end of any one of the arrays:
- Check whether the integers appointed by i, j, and k are equal or not.
- If they are equal, print any of the integers and increase i, j, and k by 1.
- Otherwise, increase the index that points to the smaller integer by 1.
Illustration:
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findCommon(int ar1[], int ar2[], int ar3[], int n1,
int n2, int n3)
{
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) {
cout << ar1[i] << " ";
i++;
j++;
k++;
}
else if (ar1[i] < ar2[j])
i++;
else if (ar2[j] < ar3[k])
j++;
else
k++;
}
}
int main()
{
int ar1[] = { 1, 5, 10, 20, 40, 80 };
int ar2[] = { 6, 7, 20, 80, 100 };
int ar3[] = { 3, 4, 15, 20, 30, 70, 80, 120 };
int n1 = sizeof(ar1) / sizeof(ar1[0]);
int n2 = sizeof(ar2) / sizeof(ar2[0]);
int n3 = sizeof(ar3) / sizeof(ar3[0]);
cout << "Common Elements are ";
findCommon(ar1, ar2, ar3, n1, n2, n3);
return 0;
}
|
C
#include <stdio.h>
void findCommon(int ar1[], int ar2[], int ar3[], int n1,
int n2, int n3)
{
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) {
printf("%d ", ar1[i]);
i++;
j++;
k++;
}
else if (ar1[i] < ar2[j])
i++;
else if (ar2[j] < ar3[k])
j++;
else
k++;
}
}
int main()
{
int ar1[] = { 1, 5, 10, 20, 40, 80 };
int ar2[] = { 6, 7, 20, 80, 100 };
int ar3[] = { 3, 4, 15, 20, 30, 70, 80, 120 };
int n1 = sizeof(ar1) / sizeof(ar1[0]);
int n2 = sizeof(ar2) / sizeof(ar2[0]);
int n3 = sizeof(ar3) / sizeof(ar3[0]);
printf("Common Elements are ");
findCommon(ar1, ar2, ar3, n1, n2, n3);
return 0;
}
|
Java
import java.io.*;
class FindCommon {
void findCommon(int ar1[], int ar2[], int ar3[])
{
int i = 0, j = 0, k = 0;
while (i < ar1.length && j < ar2.length
&& k < ar3.length) {
if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) {
System.out.print(ar1[i] + " ");
i++;
j++;
k++;
}
else if (ar1[i] < ar2[j])
i++;
else if (ar2[j] < ar3[k])
j++;
else
k++;
}
}
public static void main(String args[])
{
FindCommon ob = new FindCommon();
int ar1[] = { 1, 5, 10, 20, 40, 80 };
int ar2[] = { 6, 7, 20, 80, 100 };
int ar3[] = { 3, 4, 15, 20, 30, 70, 80, 120 };
System.out.print("Common elements are ");
ob.findCommon(ar1, ar2, ar3);
}
}
|
Python
def findCommon(ar1, ar2, ar3, n1, n2, n3):
i, j, k = 0, 0, 0
while (i < n1 and j < n2 and k < n3):
if (ar1[i] == ar2[j] and ar2[j] == ar3[k]):
print ar1[i],
i += 1
j += 1
k += 1
elif ar1[i] < ar2[j]:
i += 1
elif ar2[j] < ar3[k]:
j += 1
else:
k += 1
ar1 = [1, 5, 10, 20, 40, 80]
ar2 = [6, 7, 20, 80, 100]
ar3 = [3, 4, 15, 20, 30, 70, 80, 120]
n1 = len(ar1)
n2 = len(ar2)
n3 = len(ar3)
print "Common elements are",
findCommon(ar1, ar2, ar3, n1, n2, n3)
|
C#
using System;
class GFG {
static void findCommon(int[] ar1, int[] ar2, int[] ar3)
{
int i = 0, j = 0, k = 0;
while (i < ar1.Length && j < ar2.Length
&& k < ar3.Length) {
if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) {
Console.Write(ar1[i] + " ");
i++;
j++;
k++;
}
else if (ar1[i] < ar2[j])
i++;
else if (ar2[j] < ar3[k])
j++;
else
k++;
}
}
public static void Main()
{
int[] ar1 = { 1, 5, 10, 20, 40, 80 };
int[] ar2 = { 6, 7, 20, 80, 100 };
int[] ar3 = { 3, 4, 15, 20, 30, 70, 80, 120 };
Console.Write("Common elements are ");
findCommon(ar1, ar2, ar3);
}
}
|
Javascript
<script>
function findCommon(ar1, ar2, ar3, n1, n2, n3)
{
var i = 0,
j = 0,
k = 0;
while (i < n1 && j < n2 && k < n3)
{
if (ar1[i] == ar2[j] && ar2[j] == ar3[k])
{
document.write(ar1[i] + " ");
i++;
j++;
k++;
}
else if (ar1[i] < ar2[j]) i++;
else if (ar2[j] < ar3[k]) j++;
else k++;
}
}
var ar1 = [1, 5, 10, 20, 40, 80];
var ar2 = [6, 7, 20, 80, 100];
var ar3 = [3, 4, 15, 20, 30, 70, 80, 120];
var n1 = ar1.length;
var n2 = ar2.length;
var n3 = ar3.length;
document.write("Common Elements are ");
findCommon(ar1, ar2, ar3, n1, n2, n3);
</script>
|
PHP
<?php
function findCommon( $ar1, $ar2, $ar3,
$n1, $n2, $n3)
{
$i = 0; $j = 0; $k = 0;
while ($i < $n1 && $j < $n2 && $k < $n3)
{
if ($ar1[$i] == $ar2[$j] &&
$ar2[$j] == $ar3[$k])
{
echo $ar1[$i] , " ";
$i++;
$j++;
$k++;
}
else if ($ar1[$i] < $ar2[$j])
$i++;
else if ($ar2[$j] < $ar3[$k])
$j++;
else
$k++;
}
}
$ar1 = array(1, 5, 10, 20, 40, 80);
$ar2 = array(6, 7, 20, 80, 100);
$ar3 = array(3, 4, 15, 20, 30, 70,
80, 120);
$n1 = count($ar1);
$n2 = count($ar2);
$n3 = count($ar3);
echo "Common Elements are ";
findCommon($ar1, $ar2, $ar3,$n1, $n2, $n3);
?>
|
Output
Common Elements are 20 80
Time complexity: O(n1 + n2 + n3), In the worst case, the largest-sized array may have all small elements and the middle-sized array has all middle elements.
Auxiliary Space: O(1)
This article is compiled by Rahul Gupta
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...