# Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

```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

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
```

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array. Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.

The above solution requires extra space and two loops, we can find the common elements using a single loop and without extra space. The idea is similar to intersection of two arrays. Like two arrays loop, we run a loop and traverse three arrays.
Let the current element traversed in ar1[] be x, in ar2[] be y and in ar3[] be z. We can have following cases inside the loop.
1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.

2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element.

3) Else If y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Following are implementations of the above idea.

## C++

 `// C++ program to print common elements in three arrays ` `#include ` `using` `namespace` `std; ` ` `  `// This function prints common elements in ar1 ` `void` `findCommon(``int` `ar1[], ``int` `ar2[], ``int` `ar3[], ``int` `n1, ``int` `n2, ``int` `n3) ` `{ ` `    ``// Initialize starting indexes for ar1[], ar2[] and ar3[] ` `    ``int` `i = 0, j = 0, k = 0; ` ` `  `    ``// Iterate through three arrays while all arrays have elements ` `    ``while` `(i < n1 && j < n2 && k < n3) ` `    ``{ ` `         ``// If x = y and y = z, print any of them and move ahead  ` `         ``// in all arrays ` `         ``if` `(ar1[i] == ar2[j] && ar2[j] == ar3[k]) ` `         ``{   cout << ar1[i] << ``" "``;   i++; j++; k++; } ` ` `  `         ``// x < y ` `         ``else` `if` `(ar1[i] < ar2[j]) ` `             ``i++; ` ` `  `         ``// y < z ` `         ``else` `if` `(ar2[j] < ar3[k]) ` `             ``j++; ` ` `  `         ``// We reach here when x > y and z < y, i.e., z is smallest ` `         ``else` `             ``k++; ` `    ``} ` `} ` ` `  `// Driver program to test above function ` `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); ` `    ``int` `n2 = ``sizeof``(ar2)/``sizeof``(ar2); ` `    ``int` `n3 = ``sizeof``(ar3)/``sizeof``(ar3); ` ` `  `    ``cout << ``"Common Elements are "``; ` `    ``findCommon(ar1, ar2, ar3, n1, n2, n3); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find common elements in three arrays ` `class` `FindCommon ` `{ ` `    ``// This function prints common elements in ar1 ` `    ``void` `findCommon(``int` `ar1[], ``int` `ar2[], ``int` `ar3[]) ` `    ``{ ` `        ``// Initialize starting indexes for ar1[], ar2[] and ar3[] ` `        ``int` `i = ``0``, j = ``0``, k = ``0``; ` ` `  `        ``// Iterate through three arrays while all arrays have elements ` `        ``while` `(i < ar1.length && j < ar2.length && k < ar3.length) ` `        ``{ ` `             ``// If x = y and y = z, print any of them and move ahead ` `             ``// in all arrays ` `             ``if` `(ar1[i] == ar2[j] && ar2[j] == ar3[k]) ` `             ``{   System.out.print(ar1[i]+``" "``);   i++; j++; k++; } ` ` `  `             ``// x < y ` `             ``else` `if` `(ar1[i] < ar2[j]) ` `                 ``i++; ` ` `  `             ``// y < z ` `             ``else` `if` `(ar2[j] < ar3[k]) ` `                 ``j++; ` ` `  `             ``// We reach here when x > y and z < y, i.e., z is smallest ` `             ``else` `                 ``k++; ` `        ``} ` `    ``} ` ` `  `    ``// Driver code to test above ` `    ``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); ` `    ``} ` `} ` ` `  `/*This code is contributed by Rajat Mishra */`

## Python

 `# Python function to print common elements in three sorted arrays ` `def` `findCommon(ar1, ar2, ar3, n1, n2, n3): ` `     `  `    ``# Initialize starting indexes for ar1[], ar2[] and ar3[] ` `    ``i, j, k ``=` `0``, ``0``, ``0` `     `  `    ``# Iterate through three arrays while all arrays have elements     ` `    ``while` `(i < n1 ``and` `j < n2 ``and` `k< n3): ` `         `  `        ``# If x = y and y = z, print any of them and move ahead  ` `        ``# in all arrays ` `        ``if` `(ar1[i] ``=``=` `ar2[j] ``and` `ar2[j] ``=``=` `ar3[k]): ` `            ``print` `ar1[i], ` `            ``i ``+``=` `1` `            ``j ``+``=` `1` `            ``k ``+``=` `1` `         `  `        ``# x < y     ` `        ``elif` `ar1[i] < ar2[j]: ` `            ``i ``+``=` `1` `             `  `        ``# y < z     ` `        ``elif` `ar2[j] < ar3[k]: ` `            ``j ``+``=` `1` `         `  `        ``# We reach here when x > y and z < y, i.e., z is smallest     ` `        ``else``: ` `            ``k ``+``=` `1` ` `  `# Driver program to check above function ` `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) ` ` `  `# This code is contributed by __Devesh Agrawal__ `

## C#

 `// C# program to find common elements in ` `// three arrays ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// This function prints common element ` `    ``// s in ar1 ` `    ``static` `void` `findCommon(``int` `[]ar1, ``int` `[]ar2, ` `                                      ``int` `[]ar3) ` `    ``{ ` `         `  `        ``// Initialize starting indexes for  ` `        ``// ar1[], ar2[] and ar3[] ` `        ``int` `i = 0, j = 0, k = 0; ` ` `  `        ``// Iterate through three arrays while  ` `        ``// all arrays have elements ` `        ``while` `(i < ar1.Length && j < ar2.Length ` `                              ``&& k < ar3.Length) ` `        ``{ ` `             `  `            ``// If x = y and y = z, print any of ` `            ``// them and move ahead in all arrays ` `            ``if` `(ar1[i] == ar2[j] &&  ` `                               ``ar2[j] == ar3[k]) ` `            ``{  ` `                ``Console.Write(ar1[i] + ``" "``); ` `                ``i++; ` `                ``j++; ` `                ``k++; ` `            ``} ` ` `  `            ``// x < y ` `            ``else` `if` `(ar1[i] < ar2[j]) ` `                ``i++; ` ` `  `            ``// y < z ` `            ``else` `if` `(ar2[j] < ar3[k]) ` `                ``j++; ` ` `  `            ``// We reach here when x > y and ` `            ``// z < y, i.e., z is smallest ` `            ``else` `                ``k++; ` `        ``} ` `    ``} ` ` `  `    ``// Driver code to test above ` `    ``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); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 ` y and ` `        ``// z < y, i.e., z is smallest ` `        ``else` `            ``\$k``++; ` `    ``} ` `} ` ` `  `// Driver program to test above function ` `    ``\$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``); ` `     `  `// This code is contributed by anuj_67. ` `?> `

Output:

`Common Elements are 20 80`

Time complexity of the above solution is O(n1 + n2 + n3). In worst case, the largest sized array may have all small elements and middle sized array has all middle elements.

This article is compiled by Rahul Gupta Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Searching Arrays Searching

code

load comments