Find common elements in three sorted arrays by dictionary intersection

One way to efficiently find shared items in three sorted arrays is by using dictionary intersection. However, it’s important to note that dictionaries are commonly used for unique keys, so if there are duplicate elements in your arrays, some adjustments may be needed to make this approach work. Given three arrays sorted in non-decreasing order, print all common elements in these arrays in Python.

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:  [80, 20]

Input:  ar1 = [1, 5, 5]
             ar2 = [3, 4, 5, 5, 10]
             ar3 = [5, 5, 10, 20]
Output: [5, 5]

We have an existing solution for this problem Please refer to Find common elements in three sorted Arrays. We can solve this problem quickly in Python using the intersection of dictionaries.

Find common elements In 3 sorted Arrays using Collection.counter() Function

The approach is simple, First convert all three lists into dictionaries having elements as keys and their frequencies as value, using Counter() method. Now perform intersection operation for three dictionaries, this will result us dictionary having common elements among three array list with their frequencies.

Output:

[80, 20]

Find common elements In 3 sorted Arrays using Three Pointers

This approach uses a three-pointer approach to find common elements in the three sorted arrays. The code defines a function called common_elements. This function efficiently finds and returns the common elements among three sorted arrays by using three pointers to iterate through the arrays and comparing their elements. The function increments the pointers based on the result of the comparisons and collects common elements in a list called common. Finally, the function returns the common list.

Output:

[20, 80]
[5, 5]

Time complexity:  O(n), where n is the length of the largest input array.
Space complexity: O(1), as it only uses a fixed-size list for storing common elements.

Find common elements In 3 sorted arrays using collections.OrderedDict

In this code, we are finding the common elements among three sorted arrays namely ar1, ar2, and ar3 by using ordered dictionaries. Firstly, we initialize empty lists and create ordered dictionaries for each of the arrays in order to preserve the order of elements. Next, we iterate through the dictionaries, comparing keys (values) to identify common elements. Whenever we find a common element, we append it to a list called ‘lst’. Finally, we print the list of common elements. In this case, the common elements found are 20 and 80.

Output:

('List with common elements: ', [20, 80])

Time Complexity: O(n*n*n)
Space Complexity: O(min(n1, n2, n3))