# PHP program to print common elements in three arrays

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.