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.
Following are implementations of the above idea.
JAVA Programmming
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20find%20common%20elements%20in%20three%20arrays%0Aclass%20FindCommon%0A%7B%0A%20%20%20%20%2F%2F%20This%20function%20prints%20common%20elements%20in%20ar1%0A%20%20%20%20void%20findCommon(int%20ar1%5B%5D%2C%20int%20ar2%5B%5D%2C%20int%20ar3%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20starting%20indexes%20for%20ar1%5B%5D%2C%20ar2%5B%5D%20and%20ar3%5B%5D%0A%20%20%20%20%20%20%20%20int%20i%20%3D%200%2C%20j%20%3D%200%2C%20k%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Iterate%20through%20three%20arrays%20while%20all%20arrays%20have%20elements%0A%20%20%20%20%20%20%20%20while%20(i%20%3C%20ar1.length%20%26%26%20j%20%3C%20ar2.length%20%26%26%20k%20%3C%20ar3.length)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20%3D%20y%20and%20y%20%3D%20z%2C%20print%20any%20of%20them%20and%20move%20ahead%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20in%20all%20arrays%0A%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(ar1%5Bi%5D%20%3D%3D%20ar2%5Bj%5D%20%26%26%20ar2%5Bj%5D%20%3D%3D%20ar3%5Bk%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20%20%20System.out.print(ar1%5Bi%5D%2B%22%20%22)%3B%20%20%20i%2B%2B%3B%20j%2B%2B%3B%20k%2B%2B%3B%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20x%20%3C%20y%0A%20%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(ar1%5Bi%5D%20%3C%20ar2%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20y%20%3C%20z%0A%20%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(ar2%5Bj%5D%20%3C%20ar3%5Bk%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20We%20reach%20here%20when%20x%20%3E%20y%20and%20z%20%3C%20y%2C%20i.e.%2C%20z%20is%20smallest%0A%20%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20k%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20code%20to%20test%20above%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20FindCommon%20ob%20%3D%20new%20FindCommon()%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20ar1%5B%5D%20%3D%20%7B1%2C%205%2C%2010%2C%2020%2C%2040%2C%2080%7D%3B%0A%20%20%20%20%20%20%20%20int%20ar2%5B%5D%20%3D%20%7B6%2C%207%2C%2020%2C%2080%2C%20100%7D%3B%0A%20%20%20%20%20%20%20%20int%20ar3%5B%5D%20%3D%20%7B3%2C%204%2C%2015%2C%2020%2C%2030%2C%2070%2C%2080%2C%20120%7D%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.print(%22Common%20elements%20are%20%22)%3B%0A%20%20%20%20%20%20%20%20ob.findCommon(ar1%2C%20ar2%2C%20ar3)%3B%0A%20%20%20%20%7D%0A%7D%0A%2F*This%20code%20is%20contributed%20by%20Rajat%20Mishra%20*%2F%0A” message=”java” highlight=”” provider=”manual”/] [ad type=”banner”]