Posted on by Kalkicode
Code Array

# Find common elements in three sorted array

The problem of finding common elements in three sorted arrays involves identifying and displaying elements that exist in all three arrays simultaneously. This is a common problem encountered in data manipulation, analysis, and algorithmic challenges. In this article, we'll delve into the intricacies of solving this problem, provide a step-by-step approach, explain the algorithm, and analyze its time complexity.

## Problem Statement

Given three sorted arrays, the task is to find and display elements that are common to all three arrays.

## Example

```Consider three sorted arrays:
Array 1: [1, 9, 13, 14]
Array 2: [-5, 0, 1, 8, 9, 13, 14, 21]
Array 3: [0, 1, 8, 9, 12, 14, 21]```

The common elements among these arrays are 1, 9, and 14.

## Idea to Solve the Problem

To solve this problem, we can use a simultaneous comparison technique by iterating through all three arrays simultaneously. We'll adjust the array indices based on comparisons to ensure we consider all possible common elements.

## Pseudocode

``````common_elements(arr1, arr2, arr3, s1, s2, s3):
i, j, k = 0

while i < s1 and j < s2 and k < s3:
if arr1[i] == arr2[j] and arr2[j] == arr3[k]:
print(arr1[i])
i += 1
j += 1
k += 1
else:
if arr1[i] <= arr2[j] and arr1[i] <= arr3[k]:
i += 1
elif arr2[j] <= arr1[i] and arr2[j] <= arr3[k]:
j += 1
else:
k += 1``````

## Algorithm Explanation

1. Initialize indices `i`, `j`, and `k` to 0 to represent the current position in each array.
2. Enter a loop that continues as long as all indices `i`, `j`, and `k` are within their respective array bounds.
3. Compare the current elements at indices `i`, `j`, and `k` in the three arrays:
• If they are equal, print the common element, and increment all three indices.
• If not equal, increment the index of the array with the smallest element.
4. Repeat the above steps until one of the arrays is fully traversed.
5. The loop will terminate, and the common elements will be printed.

## Code Solution

``````// C Program
// Find common elements in three sorted array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
//Find common elements in given three arrays
void common_elements(int arr1[], int arr2[], int arr3[], int s1, int s2, int s3)
{
//Display array elements
printf("\n Array 1 :");
display(arr1, s1);
printf(" Array 2 :");
display(arr2, s2);
printf(" Array 3 :");
display(arr3, s3);
int status = 0;
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
printf(" Common element  : ");
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
//When exists common element in given array
printf(" %d ", arr1[i]);
i++;
j++;
k++;
status = 1;
}
else
{
//modify the array index when need
if (arr1[i] > arr2[j])
{
j++;
}
else if (arr3[k] > arr2[j])
{
j++;
}
else if (arr1[i] > arr3[k])
{
k++;
}
else if (arr2[j] > arr3[k])
{
k++;
}
else if (arr2[j] > arr1[i])
{
i++;
}
else if (arr3[k] > arr1[i])
{
i++;
}
}
}
if (status == 0)
{
printf(" Not Exist \n");
}
}
int main()
{
//Define array of integer elements
int arr1[] = {
1 , 9 , 13 , 14
};
int arr2[] = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
int arr3[] = {
0 , 1 , 8 , 9 , 12 , 14 , 21
};
//Get the size of array
int s1 = sizeof(arr1) / sizeof(arr1[0]);
int s2 = sizeof(arr2) / sizeof(arr2[0]);
int s3 = sizeof(arr3) / sizeof(arr3[0]);
common_elements(arr1, arr2, arr3, s1, s2, s3);
return 0;
}``````

#### Output

`````` Array 1 :  1  9  13  14
Array 2 :  -5  0  1  8  9  13  14  21
Array 3 :  0  1  8  9  12  14  21
Common element  :  1  9  14``````
``````// Java Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i] );
}
System.out.print("\n");
}
//Find all common elements in given three arrays
public void common_elements(int[] arr1, int[] arr2, int[] arr3, int s1, int s2, int s3)
{
System.out.print("\n Array 1 :");
display(arr1, s1);
System.out.print(" Array 2 :");
display(arr2, s2);
System.out.print(" Array 3 :");
display(arr3, s3);
int status = 0;
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
System.out.print(" Common element : ");
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
System.out.print(" " + arr1[i] + " ");
i++;
j++;
k++;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])
{
j++;
}
else if (arr3[k] > arr2[j])
{
j++;
}
else if (arr1[i] > arr3[k])
{
k++;
}
else if (arr2[j] > arr3[k])
{
k++;
}
else if (arr2[j] > arr1[i])
{
i++;
}
else if (arr3[k] > arr1[i])
{
i++;
}
}
}
if (status == 0)
{
System.out.print(" Not Exist \n");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array of integer elements
int[] arr1 = {
1,
9,
13,
14
};
int[] arr2 = {
-5,
0,
1,
8,
9,
13,
14,
21
};
int[] arr3 = {
0,
1,
8,
9,
12,
14,
21
};
//Get the size of array
int s1 = arr1.length;
int s2 = arr2.length;
int s3 = arr3.length;
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
}
}``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find common elements in three sorted array
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Find all common elements in given three arrays
void common_elements(int arr1[], int arr2[], int arr3[], int s1, int s2, int s3)
{
cout << "\n Array 1 :";
this->display(arr1, s1);
cout << " Array 2 :";
this->display(arr2, s2);
cout << " Array 3 :";
this->display(arr3, s3);
int status = 0;
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
cout << " Common element : ";
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
cout << " " << arr1[i] << " ";
i++;
j++;
k++;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])
{
j++;
}
else if (arr3[k] > arr2[j])
{
j++;
}
else if (arr1[i] > arr3[k])
{
k++;
}
else if (arr2[j] > arr3[k])
{
k++;
}
else if (arr2[j] > arr1[i])
{
i++;
}
else if (arr3[k] > arr1[i])
{
i++;
}
}
}
if (status == 0)
{
cout << " Not Exist \n";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
1 , 9 , 13 , 14
};
int arr2[] = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
int arr3[] = {
0 , 1 , 8 , 9 , 12 , 14 , 21
};
//Get the size of array
int s1 = sizeof(arr1) / sizeof(arr1[0]);
int s2 = sizeof(arr2) / sizeof(arr2[0]);
int s3 = sizeof(arr3) / sizeof(arr3[0]);
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
return 0;
}``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````//Include namespace system
using System;
// C# Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Find all common elements in given three arrays
public void common_elements(int[] arr1, int[] arr2, int[] arr3, int s1, int s2, int s3)
{
Console.Write("\n Array 1 :");
display(arr1, s1);
Console.Write(" Array 2 :");
display(arr2, s2);
Console.Write(" Array 3 :");
display(arr3, s3);
int status = 0;
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
Console.Write(" Common element : ");
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
Console.Write(" " + arr1[i] + " ");
i++;
j++;
k++;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])
{
j++;
}
else if (arr3[k] > arr2[j])
{
j++;
}
else if (arr1[i] > arr3[k])
{
k++;
}
else if (arr2[j] > arr3[k])
{
k++;
}
else if (arr2[j] > arr1[i])
{
i++;
}
else if (arr3[k] > arr1[i])
{
i++;
}
}
}
if (status == 0)
{
Console.Write(" Not Exist \n");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
1 , 9 , 13 , 14
};
int[] arr2 = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
int[] arr3 = {
0 , 1 , 8 , 9 , 12 , 14 , 21
};
//Get the size of array
int s1 = arr1.Length;
int s2 = arr2.Length;
int s3 = arr3.Length;
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
}
}``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````<?php
// Php Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
public	function display( \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
//Find all common elements in given three arrays
public	function common_elements( \$arr1, \$arr2, \$arr3, \$s1, \$s2, \$s3)
{
echo "\n Array 1 :";
\$this->display(\$arr1, \$s1);
echo " Array 2 :";
\$this->display(\$arr2, \$s2);
echo " Array 3 :";
\$this->display(\$arr3, \$s3);
\$status = 0;
//Loop controlling variables
\$i = 0;
\$j = 0;
\$k = 0;
echo " Common element : ";
while (\$i < \$s1 && \$j < \$s2 && \$k < \$s3)
{
if (\$arr1[\$i] == \$arr2[\$j] && \$arr2[\$j] == \$arr3[\$k])
{
echo " ". \$arr1[\$i] ." ";
\$i++;
\$j++;
\$k++;
\$status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (\$arr1[\$i] > \$arr2[\$j])
{
\$j++;
}
else if (\$arr3[\$k] > \$arr2[\$j])
{
\$j++;
}
else if (\$arr1[\$i] > \$arr3[\$k])
{
\$k++;
}
else if (\$arr2[\$j] > \$arr3[\$k])
{
\$k++;
}
else if (\$arr2[\$j] > \$arr1[\$i])
{
\$i++;
}
else if (\$arr3[\$k] > \$arr1[\$i])
{
\$i++;
}
}
}
if (\$status == 0)
{
echo " Not Exist \n";
}
}
}

function main()
{
\$obj = new MyArray();
//Define array of integer elements
\$arr1 = array(1, 9, 13, 14);
\$arr2 = array(-5, 0, 1, 8, 9, 13, 14, 21);
\$arr3 = array(0, 1, 8, 9, 12, 14, 21);
//Get the size of array
\$s1 = count(\$arr1);
\$s2 = count(\$arr2);
\$s3 = count(\$arr3);
\$obj->common_elements(\$arr1, \$arr2, \$arr3, \$s1, \$s2, \$s3);
}
main();``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````// Node Js Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Find all common elements in given three arrays
common_elements(arr1, arr2, arr3, s1, s2, s3)
{
process.stdout.write("\n Array 1 :");
this.display(arr1, s1);
process.stdout.write(" Array 2 :");
this.display(arr2, s2);
process.stdout.write(" Array 3 :");
this.display(arr3, s3);
var status = 0;
//Loop controlling variables
var i = 0;
var j = 0;
var k = 0;
process.stdout.write(" Common element : ");
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
process.stdout.write(" " + arr1[i] + " ");
i++;
j++;
k++;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])
{
j++;
}
else if (arr3[k] > arr2[j])
{
j++;
}
else if (arr1[i] > arr3[k])
{
k++;
}
else if (arr2[j] > arr3[k])
{
k++;
}
else if (arr2[j] > arr1[i])
{
i++;
}
else if (arr3[k] > arr1[i])
{
i++;
}
}
}
if (status == 0)
{
process.stdout.write(" Not Exist \n");
}
}
}

function main()
{
var obj = new MyArray();
//Define array of integer elements
var arr1 = [1, 9, 13, 14];
var arr2 = [-5, 0, 1, 8, 9, 13, 14, 21];
var arr3 = [0, 1, 8, 9, 12, 14, 21];
//Get the size of array
var s1 = arr1.length;
var s2 = arr2.length;
var s3 = arr3.length;
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
}
main();``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````#  Python 3 Program
#  Find common elements in three sorted array
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

# Find all common elements in given three arrays
def common_elements(self, arr1, arr2, arr3, s1, s2, s3) :
print("\n Array 1 :", end = "")
self.display(arr1, s1)
print(" Array 2 :", end = "")
self.display(arr2, s2)
print(" Array 3 :", end = "")
self.display(arr3, s3)
status = 0
# Loop controlling variables
i = 0
j = 0
k = 0
print(" Common element : ", end = "")
while (i < s1 and j < s2 and k < s3) :
if (arr1[i] == arr2[j] and arr2[j] == arr3[k]) :
print(" ", arr1[i] ," ", end = "")
i += 1
j += 1
k += 1
status = 1
else :
# Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j]) :
j += 1

elif(arr3[k] > arr2[j]) :
j += 1

elif(arr1[i] > arr3[k]) :
k += 1

elif(arr2[j] > arr3[k]) :
k += 1

elif(arr2[j] > arr1[i]) :
i += 1

elif(arr3[k] > arr1[i]) :
i += 1

if (status == 0) :
print(" Not Exist \n", end = "")

def main() :
obj = MyArray()
# Define array of integer elements
arr1 = [1, 9, 13, 14]
arr2 = [-5, 0, 1, 8, 9, 13, 14, 21]
arr3 = [0, 1, 8, 9, 12, 14, 21]
# Get the size of array
s1 = len(arr1)
s2 = len(arr2)
s3 = len(arr3)
obj.common_elements(arr1, arr2, arr3, s1, s2, s3)

if __name__ == "__main__": main()``````

#### Output

`````` Array 1 :  1  9  13  14
Array 2 :  -5  0  1  8  9  13  14  21
Array 3 :  0  1  8  9  12  14  21
Common element :   1    9    14``````
``````#  Ruby Program
#  Find common elements in three sorted array
class MyArray

# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
print("\n")
end
# Find all common elements in given three arrays
def common_elements(arr1, arr2, arr3, s1, s2, s3)

print("\n Array 1 :")
self.display(arr1, s1)
print(" Array 2 :")
self.display(arr2, s2)
print(" Array 3 :")
self.display(arr3, s3)
status = 0
# Loop controlling variables
i = 0
j = 0
k = 0
print(" Common element : ")
while (i < s1 && j < s2 && k < s3)

if (arr1[i] == arr2[j] && arr2[j] == arr3[k])

print(" ", arr1[i] ," ")
i += 1
j += 1
k += 1
status = 1
else

# Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])

j += 1
elsif(arr3[k] > arr2[j])

j += 1
elsif(arr1[i] > arr3[k])

k += 1
elsif(arr2[j] > arr3[k])

k += 1
elsif(arr2[j] > arr1[i])

i += 1
elsif(arr3[k] > arr1[i])

i += 1
end
end
end
if (status == 0)

print(" Not Exist \n")
end
end
end
def main()

obj = MyArray.new()
# Define array of integer elements
arr1 = [1, 9, 13, 14]
arr2 = [-5, 0, 1, 8, 9, 13, 14, 21]
arr3 = [0, 1, 8, 9, 12, 14, 21]
# Get the size of array
s1 = arr1.length
s2 = arr2.length
s3 = arr3.length
obj.common_elements(arr1, arr2, arr3, s1, s2, s3)
end
main()``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14 ``````
``````// Scala Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Find all common elements in given three arrays
def common_elements(arr1: Array[Int], arr2: Array[Int], arr3: Array[Int], s1: Int, s2: Int, s3: Int): Unit = {
print("\n Array 1 :");
display(arr1, s1);
print(" Array 2 :");
display(arr2, s2);
print(" Array 3 :");
display(arr3, s3);
var status: Int = 0;
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
print(" Common element : ");
while (i < s1 && j < s2 && k < s3)
{
if (arr1(i) == arr2(j) && arr2(j) == arr3(k))
{
print(" " + arr1(i) + " ");
i += 1;
j += 1;
k += 1;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1(i) > arr2(j))
{
j += 1;
}
else if (arr3(k) > arr2(j))
{
j += 1;
}
else if (arr1(i) > arr3(k))
{
k += 1;
}
else if (arr2(j) > arr3(k))
{
k += 1;
}
else if (arr2(j) > arr1(i))
{
i += 1;
}
else if (arr3(k) > arr1(i))
{
i += 1;
}
}
}
if (status == 0)
{
print(" Not Exist \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array of integer elements
var arr1: Array[Int] = Array(1, 9, 13, 14);
var arr2: Array[Int] = Array(-5, 0, 1, 8, 9, 13, 14, 21);
var arr3: Array[Int] = Array(0, 1, 8, 9, 12, 14, 21);
//Get the size of array
var s1: Int = arr1.length;
var s2: Int = arr2.length;
var s3: Int = arr3.length;
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
}
}``````

#### Output

`````` Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Array 3 : 0 1 8 9 12 14 21
Common element :  1  9  14``````
``````// Swift Program
// Find common elements in three sorted array
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find all common elements in given three arrays
func common_elements(_ arr1: [Int], _ arr2: [Int], _ arr3: [Int], _ s1: Int, _ s2: Int, _ s3: Int)
{
print("\n Array 1 :", terminator: "");
self.display(arr1, s1);
print(" Array 2 :", terminator: "");
self.display(arr2, s2);
print(" Array 3 :", terminator: "");
self.display(arr3, s3);
var status: Int = 0;
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
print(" Common element : ", terminator: "");
while (i < s1 && j < s2 && k < s3)
{
if (arr1[i] == arr2[j] && arr2[j] == arr3[k])
{
print(" ", arr1[i] ," ", terminator: "");
i += 1;
j += 1;
k += 1;
status = 1;
}
else
{
//Modify the array index [i,j,k] when need
if (arr1[i] > arr2[j])
{
j += 1;
}
else if (arr3[k] > arr2[j])
{
j += 1;
}
else if (arr1[i] > arr3[k])
{
k += 1;
}
else if (arr2[j] > arr3[k])
{
k += 1;
}
else if (arr2[j] > arr1[i])
{
i += 1;
}
else if (arr3[k] > arr1[i])
{
i += 1;
}
}
}
if (status == 0)
{
print(" Not Exist \n", terminator: "");
}
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array of integer elements
let arr1: [Int] = [1, 9, 13, 14];
let arr2: [Int] = [-5, 0, 1, 8, 9, 13, 14, 21];
let arr3: [Int] = [0, 1, 8, 9, 12, 14, 21];
//Get the size of array
let s1: Int = arr1.count;
let s2: Int = arr2.count;
let s3: Int = arr3.count;
obj.common_elements(arr1, arr2, arr3, s1, s2, s3);
}
main();``````

#### Output

`````` Array 1 :  1  9  13  14
Array 2 :  -5  0  1  8  9  13  14  21
Array 3 :  0  1  8  9  12  14  21
Common element :   1    9    14``````

## Time Complexity Analysis

The algorithm iterates through the arrays simultaneously, and at each step, it adjusts the indices based on comparisons. Since each element is compared only once and the array indices are updated in a linear manner, the time complexity is O(n), where `n` is the size of the largest array. This linear time complexity ensures efficient performance even for large arrays.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post