Prerequisite: Sets in Python Given three arrays, we have to find common elements in three sorted lists using sets. 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]
Method 1: We have given three arrays, with the help of sets one can easily find out the intersection of these Arrays. Intersection method simply provides the intersection of both the arrays upon which you want to perform the operation of intersection (or, it simply gives out the common elements in both the array). We will be taking three arrays and then we will take out the intersection. Below is the implementation of above approach :
Python3
# Python3 program to find common elements# in three lists using setsdef IntersecOfSets(arr1, arr2, arr3): # Converting the arrays into sets s1 = set(arr1) s2 = set(arr2) s3 = set(arr3) # Calculates intersection of # sets on s1 and s2 set1 = s1.intersection(s2) #[80, 20, 100] # Calculates intersection of sets # on set1 and s3 result_set = set1.intersection(s3) # Converts resulting set to list final_list = list(result_set) print(final_list)# Driver Codeif __name__ == '__main__' : # Elements in Array1 arr1 = [1, 5, 10, 20, 40, 80, 100] # Elements in Array2 arr2 = [6, 7, 20, 80, 100] # Elements in Array3 arr3 = [3, 4, 15, 20, 30, 70, 80, 120] # Calling Function IntersecOfSets(arr1, arr2, arr3) |
[80, 20]
Time complexity: O(n), where n is the size of the largest input array.
Auxiliary space: O(m), where m is the size of the resulting set.
Method 2: Using Set
One alternative approach using sets is to iterate over the elements in one of the lists and check if they are present in the other two lists using the in operator. If an element is present in all three lists, it can be added to a new set or list to store the common elements.
For example:
Python3
def find_common(list1, list2, list3): common = set() for elem in list1: if elem in list2 and elem in list3: common.add(elem) return commonlist1 = [1, 5, 10, 20, 40, 80]list2 = [6, 7, 20, 80, 100]list3 = [3, 4, 15, 20, 30, 70, 80, 120]common = find_common(list1, list2, list3)print(common) |
{80, 20}
Time complexity: O(n), where n is the size of list1.
Auxiliary space: O(m), where m is the size of the set of common elements
Method 3: Here is another approach using list comprehension and the intersection method of sets:
Python3
def find_common(list1, list2, list3): # Convert lists to sets set1 = set(list1) set2 = set(list2) set3 = set(list3) # Use list comprehension to find common elements # in all three sets and return as a list return [elem for elem in set1 if elem in set2 and elem in set3]list1 = [1, 5, 10, 20, 40, 80]list2 = [6, 7, 20, 80, 100]list3 = [3, 4, 15, 20, 30, 70, 80, 120]common = find_common(list1, list2, list3)print(common) |
[80, 20]
Time complexity: O(n), where n is the total number of elements in the three lists.
Auxiliary space: O(n)
Method 4: Use a loop to iterate over the elements of one list and check if they exist in the other two lists. Here’s an example:
Python3
def IntersecOfSets(arr1, arr2, arr3): result = [] for i in arr1: if i in arr2 and i in arr3: result.append(i) print(list(set(result))) arr1 = [1, 5, 10, 20, 40, 80]arr2 = [6, 7, 20, 80, 100]arr3 = [3, 4, 15, 20, 30, 70, 80, 120]common = IntersecOfSets(arr1, arr2, arr3) |
[20, 80]
Time complexity: O(n^2), where n is the length of the largest input list.
Auxiliary space: O(m), where m is the size of the resulting list.
Method 5: Using the built-in function filter() and lambda function to find the intersection of the arrays.
- Define a lambda function that takes an element as an argument and checks if it is present in all three arrays.
- Use the filter() function to apply the lambda function to each element of the first array and return only those elements that satisfy the condition.
- Convert the filtered result into a list and return it as the intersection of the three arrays.
Python3
def IntersecOfSets(arr1, arr2, arr3): common = list(filter(lambda x: x in arr2 and x in arr3, arr1)) print(common)arr1 = [1, 5, 10, 20, 40, 80]arr2 = [6, 7, 20, 80, 100]arr3 = [3, 4, 15, 20, 30, 70, 80, 120]IntersecOfSets(arr1, arr2, arr3) |
[20, 80]
Time complexity: O(n) where n is the length of the first array (assuming constant time set lookup and set intersection operations).
Auxiliary space: O(m) where m is the number of elements that are common in all three arrays (assuming worst-case scenario where all elements are common).
