💡 Problem Formulation: Given three sorted arrays, the task is to identify the common elements present in all three arrays efficiently. For example, suppose we have arrays A = [1,2,5,6], B = [2,3,5,7], and C = [2,4,5,8]. The common elements in these arrays are [2,5], which should be the return value of the solution.
Method 1: Use Dictionary from Counters
To find common elements in three sorted arrays using Python, you can create dictionaries from arrays by utilizing the Collections.Counter class, which counts the occurrences of each element in each array. By performing dictionary intersection, you can efficiently obtain the common elements.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
from collections import Counter
def common_elements(arr1, arr2, arr3):
dict1 = Counter(arr1)
dict2 = Counter(arr2)
dict3 = Counter(arr3)
result_dict = dict1 & dict2 & dict3
return list(result_dict.elements())
# Example usage
arr1 = [1, 2, 5, 6]
arr2 = [2, 3, 5, 7]
arr3 = [2, 4, 5, 8]
print(common_elements(arr1, arr2, arr3))The output:
[2, 5]
The function common_elements creates Counter dictionaries from three input arrays. The & operator is used to compute the intersection of these Counters. The result is converted back to a list using the elements() method and returned. This method is fast and concise when dealing with sorted arrays.
Method 2: Dictionary Intersection from Dictionary Comprehensions
This method involves creating dictionaries with element frequency using dictionary comprehensions and then performing the intersection operation. This allows for exploitation of dictionary intersection methods which can identify common keys quickly and efficiently.
Here’s an example:
def common_elements(arr1, arr2, arr3):
dict1 = {i: arr1.count(i) for i in arr1}
dict2 = {i: arr2.count(i) for i in arr2}
dict3 = {i: arr3.count(i) for i in arr3}
common_keys = dict1.keys() & dict2.keys() & dict3.keys()
return list(common_keys)
# Example usage
arr1 = [1, 2, 5, 6]
arr2 = [2, 3, 5, 7]
arr3 = [2, 4, 5, 8]
print(common_elements(arr1, arr2, arr3))The output:
[2, 5]
The function common_elements computes dictionaries representing the frequency of each element in the arrays. The intersection of the keys of these dictionaries yields the common elements, since dictionaries are inherently fast for lookups, this method is also quite performant especially with sorted arrays where counting is more optimized.
Method 3: Using Set Intersection
Set intersection is a straightforward and effective approach to finding common elements. Convert each array to a set and apply the intersection (&) operator to these sets to find common elements.
Here’s an example:
def common_elements(arr1, arr2, arr3):
set1 = set(arr1)
set2 = set(arr2)
set3 = set(arr3)
common_elements_set = set1 & set2 & set3
return list(common_elements_set)
# Example usage
arr1 = [1, 2, 5, 6]
arr2 = [2, 3, 5, 7]
arr3 = [2, 4, 5, 8]
print(common_elements(arr1, arr2, arr3))The output:
[2, 5]
The function common_elements first converts the input arrays into sets. It then uses set intersection to find common elements. While converting to a set loses the sorted nature of the arrays, this method is typically very efficient due to Python’s optimized set operations.
Method 4: Traditional Loop and Comparison
In this method, we use a more traditional approach by iterating through each array and comparing elements to find common items. This is a brute force method and while less efficient, it is straightforward and does not require additional data structures.
Here’s an example:
def common_elements(arr1, arr2, arr3):
common = []
i, j, k = 0, 0, 0
while i < len(arr1) and j < len(arr2) and k < len(arr3):
if arr1[i] == arr2[j] == arr3[k]:
common.append(arr1[i])
i += 1
j += 1
k += 1
elif arr1[i] < arr2[j]:
i += 1
elif arr2[j] < arr3[k]:
j += 1
else:
k += 1
return common
# Example usage
arr1 = [1, 2, 5, 6]
arr2 = [2, 3, 5, 7]
arr3 = [2, 4, 5, 8]
print(common_elements(arr1, arr2, arr3))The output:
[2, 5]
The common_elements function iterates through the arrays simultaneously while maintaining three separate indices. When a common element is found, it is added to the result list, and the indices are incremented. If elements don’t match, the smallest one is increased to keep the searching efficient, leveraging the sorted nature of the input arrays.
Bonus One-Liner Method 5: Using List Comprehension with Set Intersection
If you prefer a more concise one-liner, Python allows you to combine set intersection with list comprehension to find common elements in sorted arrays.
Here’s an example:
arr1 = [1, 2, 5, 6] arr2 = [2, 3, 5, 7] arr3 = [2, 4, 5, 8] common_elements = list(set(arr1) & set(arr2) & set(arr3)) print(common_elements)
The output:
[2, 5]
This line of code is a concise and pythonic way to compute the intersection of three arrays by converting them into sets and performing the intersection operation. It is then converted back into a list and printed out. This method benefits from the efficiency of set operations in Python.
Summary/Discussion
- Method 1: Using Dictionary from Counters. This method is highly efficient for sorted arrays and leverages Python’s optimized Counter class. However, it involves the creation of temporary dictionary structures.
- Method 2: Dictionary Intersection from Dictionary Comprehensions. Similar advantages as Method 1 but can be less performance-efficient due to needing to count elements in each array separately for the dictionary.
- Method 3: Using Set Intersection. Extremely efficient for finding common elements due to Python’s optimized set operations. However, converting to a set does not maintain the order of elements.
- Method 4: Traditional Loop and Comparison. Straightforward, no additional data structure, preserves the order of arrays, but has a higher time complexity compared to other methods.
- Bonus One-Liner Method 5: Using List Comprehension with Set Intersection. Offers elegance and conciseness but like Method 3 loses the order of elements.