Given two lists, print all the common elements of two lists.
Examples:
Input : list1 = [1, 2, 3, 4, 5]
list2 = [5, 6, 7, 8, 9]
Output : {5}
Explanation: The common element of the lists is 5.
Input : list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9]
Output : No common elements
Explanation: They do not have any
elements in common in between them
Method 1:Using Set’s & property
Convert the lists to sets and then print set1&set2. set1&set2 returns the common elements set, where set1 is the list1 and set2 is the list2.
Below is the Python3 implementation of the above approach:
Python3
# Python program to find the common elements# in two listsdef common_member(a, b): a_set = set(a) b_set = set(b) if (a_set & b_set): print(a_set & b_set) else: print("No common elements") a = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]common_member(a, b) a = [1, 2, 3, 4, 5]b = [6, 7, 8, 9]common_member(a, b) |
Output:
{5}
No common elements
Time complexity: O(n), where n is the size of the larger input list.
Auxiliary space: O(n), where n is the total number of unique elements in both input lists. .
Method 2:Using Set’s intersection property
Convert the list to set by conversion. Use the intersection function to check if both sets have any elements in common. If they have many elements in common, then print the intersection of both sets.
Below is the Python3 implementation of the above approach:
Python3
# Python program to find common elements in# both sets using intersection function in# sets# functiondef common_member(a, b): a_set = set(a) b_set = set(b) # check length if len(a_set.intersection(b_set)) > 0: return(a_set.intersection(b_set)) else: return("no common elements") a = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]print(common_member(a, b)) a =[1, 2, 3, 4, 5]b =[6, 7, 8, 9]print(common_member(a, b)) |
Output:
{5}
No common elements
Time complexity: O(n), where n is the total number of elements in both sets.
Auxiliary space: O(n), where n is the total number of elements in both sets (used to create the two sets).
Method 3: Using for loop
Python
def common_member(a, b): result = [i for i in a if i in b] return resulta = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]print("The common elements in the two lists are: ")print(common_member(a, b)) |
Output:
The common elements in the two lists are: [5]
Time complexity: O(n*m), where n is the length of list a and m is the length of list b.
Auxiliary space: O(k), where k is the length of the resulting list.
Method 4: Using collections
This code uses the collections module to create two Counter objects from the two lists, a and b. The & operator is then used to return the common elements from the two lists. The result is then printed out.
Python3
import collectionsdef common_member(a, b): result = collections.Counter(a) & collections.Counter(b) return result.keys() a = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9] print("The common elements in the two lists are: ")print(common_member(a, b)) |
The common elements in the two lists are: dict_keys([5])
The time complexity of the given code is O(m + n), where m and n are the lengths of lists a and b, respectively.
The space complexity of the function is also O(m + n), as it creates two Counter objects of length m and n, respectively.
Method 5: Using operator.countOf()
Python3
import operator as opdef common_member(a, b): result = [i for i in a if op.countOf(b,i)>0 ] return resulta = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]print("The common elements in the two lists are: ")print(common_member(a, b)) |
The common elements in the two lists are: [5]
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 6: Use a dictionary to count the occurrence of each element in both sets, and then return the elements that appear in both sets
- Create an empty dictionary common_dict to store the count of each element that appears in both sets.
- Loop through each element in the first set (a) and check if it is already in the dictionary common_dict. If it is, increment its count by 1; otherwise, add it to the dictionary with a count of 1.
- Loop through each element in the second set (b) and follow the same steps as above.
- Create a new list common that contains all elements in the dictionary that have a count of 2 (i.e., appear in both sets).
- Check if the length of the list common is greater than 0. If it is, return the list; otherwise, return a message saying “no common elements”.
- Call the function with two sample sets a and b.
- Print the result of the function for each set of input.
Python3
def common_member(a, b): # create an empty dictionary to store the count of each element common_dict = {} for elem in a: # if the element is already in the dictionary if elem in common_dict: # increment the count common_dict[elem] += 1 # if the element is not in the dictionary else: common_dict[elem] = 1 # add it to the dictionary with a count of 1 for elem in b: # loop through each element in the second set if elem in common_dict: # if the element is already in the dictionary common_dict[elem] += 1 # increment the count else: # if the element is not in the dictionary common_dict[elem] = 1 # add it to the dictionary with a count of 1 # create a list of elements that have a count of 2 in the dictionary common = [elem for elem in common_dict if common_dict[elem] == 2] if len(common) > 0: # if there are common elements return common # return the list of common elements else: # if there are no common elements return "no common elements" # return a message saying soa = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]print(common_member(a, b))a = [1, 2, 3, 4, 5]b = [6, 7, 8, 9]print(common_member(a, b)) |
[5] no common elements
Time complexity: O(m+n), where m is the length of the first set (a) and n is the length of the second set (b). This is because the implementation requires looping through both sets once to count the occurrence of each element.
Auxiliary space: O(m+n), where m is the length of the first set (a) and n is the length of the second set (b).
Method 7: Using NumPy
Step-by-step approach:
- Convert the two input lists, a and b, to NumPy arrays using the np.array() function.
- Use the np.intersect1d() function to find the common elements between the two arrays. This function returns a sorted, unique array of common elements.
- Convert the resulting NumPy array to a Python list using the list() function.
- Return the resulting list of common elements.
Python3
import numpy as npdef common_member(a, b): return list(np.intersect1d(a, b))# Example usage:a = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]common_elements = common_member(a, b)print(common_elements)# Output: [5]a = [1, 2, 3, 4, 5]b = [6, 7, 8, 9]common_elements = common_member(a, b)print(common_elements)# Output: []#This code is contributed by Vinay Pinjala. |
Output
[5] []
Time complexity: O(n log n), where n is the total number of elements in both lists. The np.intersect1d() function has a time complexity of O(n log n) due to its use of sorting algorithms. The conversion of the NumPy array to a Python list has a time complexity of O(n).
Auxiliary space: O(n), where n is the total number of elements in both lists. This is because the function creates two NumPy arrays, one for each input list, which have a total size of O(n).
Method 8: Using itertools
Here’s the implementation of finding the common elements of two lists using itertools.filterfalse(), along with the algorithm and time and space complexity analysis:
Algorithm:
Convert both lists into sets.
Using filterfalse() from the itertools module, create a new set containing the elements in a_set that are not in b_set, and a new set containing the elements in b_set that are not in a_set.
Create a new set containing the intersection of the two sets from step 2.
Return the set from step 3 as a list.
Python3
# Python program to find common elements in# both sets using iTERTOOLS import itertoolsdef common_member(a, b): a_set = set(a) b_set = set(b) #Using filterfalse not_in_a = set(itertools.filterfalse(lambda x: x in a_set, b_set)) not_in_b = set(itertools.filterfalse(lambda x: x in b_set, a_set)) result = set(a_set).intersection(set(b_set) - not_in_a).union(set(b_set).intersection(set(a_set) - not_in_b)) return list(result)# Example usage:a = [1, 2, 3, 4, 5]b = [5, 6, 7, 8, 9]print("The common elements in the two lists are: ")print(common_member(a, b))# Example usage:a = [1, 2, 3, 4, 5]b = [6, 7, 8, 9]print("The common elements in the two lists are: ")print(common_member(a, b)) |
The common elements in the two lists are: [5] The common elements in the two lists are: []
Time Complexity: O(n+m), where n and m are the lengths of the input lists. This is because the set() function takes O(n) time to convert each list to a set, and filterfalse() takes O(n+m) time to compute the differences between the two sets.
Auxiliary Space: O(n+m), where n and m are the lengths of the input lists. This is because we create two sets of length n and m, respectively.
