Given three arrays sorted in non-decreasing order, print all common elements in these arrays.<\/p>\n
Examples:<\/p>\n
ar1[] = {1, 5, 10, 20, 40, 80}
\nar2[] = {6, 7, 20, 80, 100}
\nar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
\nOutput: 20, 80<\/p>\n
ar1[] = {1, 5, 5} 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. Following are implementations of the above idea.<\/p>\n Python Programmming<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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\u201d message=\u201dpython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":" PYTHON Programming-Find common elements in three sorted arrays – Searching and sorting – 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. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,83517,71670],"tags":[70235,72892,72869,72900,72899,72887,72903,72696,72877,72908,72819,72890,72891,72911,72907,72870,72876,72879,72918,72895,72874,72883,72894,72916,72915,72917,70891,72898,72989,72909,72886,72888,72896,72913,72872,72897,72990,72871,72880,72875,72901,72893,72904,72889,72910,72878,72884,72882,72873,72881,72914,72912,72885],"class_list":["post-25342","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-python-programming","category-searching-and-sorting","tag-algorithm-examples","tag-algorithm-to-find-largest-of-n-numbers","tag-c-programming-kth-smallestlargest-element-in-unsorted-array","tag-cluster-random-sampling","tag-element-n","tag-find-kth-smallest-element-in-array-java","tag-find-kth-smallest-element-in-two-sorted-arrays","tag-find-largest-number-in-array-java","tag-find-max-value-in-array-java","tag-find-median","tag-find-minimum-value-in-array-java","tag-find-smallest-number-in-array","tag-find-smallest-number-in-array-java","tag-find-the-mean","tag-find-the-median","tag-k-element","tag-k-sel","tag-kth-element","tag-kth-number","tag-kth-smallest-element-in-array","tag-largest-element","tag-largest-element-in-an-array","tag-least-element","tag-max-value-in-array-java","tag-median-of-two-sorted-arrays","tag-methods-of-sampling-in-statistics","tag-min-heap","tag-population-vs-sample","tag-python-programming-kth-smallestlargest-element-in-unsorted-array","tag-quick-select","tag-sample-in-statistics","tag-sample-statistic","tag-sample-statistics","tag-sample-vs-population","tag-sampling-techniques-in-statistics","tag-sampling-types","tag-select-max-n-element","tag-smallest-element","tag-statistical-sampling","tag-statistics-examples","tag-systematic-random-sampling","tag-systematic-sampling","tag-systematic-sampling-definition","tag-th-element","tag-the-smallest-element","tag-tj-maxx","tag-types-of-sampling","tag-types-of-sampling-methods","tag-types-of-sampling-techniques","tag-types-of-statistics","tag-unsorted","tag-what-is-a-stratified-sample","tag-what-is-systematic-sampling"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25342","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25342"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25342\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nar2[] = {3, 4, 5, 5, 10}
\nar3[] = {5, 5, 10, 20}
\nOutput:<\/strong> 5, 5
\nA 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.<\/p>\n
\nLet 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.
\n1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
\n2) 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.<\/p>\n[ad type=\u201dbanner\u201d]\n