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 < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

[ad type=”banner”]

Following are implementations of the above idea.

Python Programmming

[pastacode lang=”python” manual=”%23%20Python%20function%20to%20print%20common%20elements%20in%20three%20sorted%20arrays%0Adef%20findCommon(ar1%2C%20ar2%2C%20ar3%2C%20n1%2C%20n2%2C%20n3)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Initialize%20starting%20indexes%20for%20ar1%5B%5D%2C%20ar2%5B%5D%20and%20ar3%5B%5D%0A%20%20%20%20i%2C%20j%2C%20k%20%3D%200%2C%200%2C%200%0A%20%20%20%20%20%0A%20%20%20%20%23%20Iterate%20through%20three%20arrays%20while%20all%20arrays%20have%20elements%20%20%20%20%0A%20%20%20%20while%20(i%20%3C%20n1%20and%20j%20%3C%20n2%20and%20k%3C%20n3)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20x%20%3D%20y%20and%20y%20%3D%20z%2C%20print%20any%20of%20them%20and%20move%20ahead%20%0A%20%20%20%20%20%20%20%20%23%20in%20all%20arrays%0A%20%20%20%20%20%20%20%20if%20(ar1%5Bi%5D%20%3D%3D%20ar2%5Bj%5D%20and%20ar2%5Bj%5D%20%3D%3D%20ar3%5Bk%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20ar1%5Bi%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20k%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20x%20%3C%20y%20%20%20%20%0A%20%20%20%20%20%20%20%20elif%20ar1%5Bi%5D%20%3C%20ar2%5Bj%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20y%20%3C%20z%20%20%20%20%0A%20%20%20%20%20%20%20%20elif%20ar2%5Bj%5D%20%3C%20ar3%5Bk%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20We%20reach%20here%20when%20x%20%3E%20y%20and%20z%20%3C%20y%2C%20i.e.%2C%20z%20is%20smallest%20%20%20%20%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20k%20%2B%3D%201%0A%20%0A%23%20Driver%20program%20to%20check%20above%20function%0Aar1%20%3D%20%5B1%2C%205%2C%2010%2C%2020%2C%2040%2C%2080%5D%0Aar2%20%3D%20%5B6%2C%207%2C%2020%2C%2080%2C%20100%5D%0Aar3%20%3D%20%5B3%2C%204%2C%2015%2C%2020%2C%2030%2C%2070%2C%2080%2C%20120%5D%0An1%20%3D%20len(ar1)%0An2%20%3D%20len(ar2)%0An3%20%3D%20len(ar3)%0Aprint%20%22Common%20elements%20are%22%2C%0AfindCommon(ar1%2C%20ar2%2C%20ar3%2C%20n1%2C%20n2%2C%20n3)%0A%20%0A%23%20This%20code%20is%20contributed%20by%20__Devesh%20Agrawal__%0A” message=”python” highlight=”” provider=”manual”/] [ad type=”banner”]