Given three arrays sorted 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

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.

- If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
- Else If x < y, we can move ahead in ar1[] as x cannot be a common element.
- Else If x > z and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Below is the implementation of the above approach:

- PHP

`<?php`

`// PHP program to print common elements`

`// in three arrays`

`// This function prints common elements`

`// in ar1`

`function`

`findCommon( `

`$ar1`

`, `

`$ar2`

`, `

`$ar3`

`,`

` `

`$n1`

`, `

`$n2`

`, `

`$n3`

`)`

`{`

` `

` `

`// Initialize starting indexes for`

` `

`// ar1[], ar2[] and ar3[]`

` `

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

`])`

` `

`{`

` `

`echo`

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

` `

`$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 of the above solution is **O(n1 + n2 + n3)**. In the worst case, the largest sized array may have all small elements and middle-sized array has all middle elements.