Sometimes we encounter the problem of checking if one list contains any element of another list. This kind of problem is quite popular in competitive programming. Let’s discuss various ways to achieve this particular task.
Method #1: Using any()
Python3
# Python code to check if two lists# have any element in common# Initialization of listlist1 = [1, 2, 3, 4, 55]list2 = [2, 3, 90, 22]# using any functionout = any(check in list1 for check in list2)# Checking conditionif out: print("True") else : print("False") |
True
Time complexity: O(n*m), where n and m are the lengths of list1 and list2 respectively.
Auxiliary space: O(1), as only a few variables are used and no additional data structures are created.
Method #2: Using in operator.
Python3
# Python code to check if two lists# have any element in common# Initialization of listlist1 = [1, 3, 4, 55]list2 = [90, 22]flag = 0# Using in to check element of# second list into first listfor elem in list2: if elem in list1: flag = 1# checking conditionif flag == 1: print("True") else : print("False") |
False
Time Complexity: O(n), where n is length of list.
Auxiliary Space: O(1)
Method#3: Using set()
Python3
# Python code to check if two lists# have any element in common# Initialization of listlist1 = [1, 2, 3, 4, 55]list2 = [2, 3, 90, 22]# using setout = set(list1) & set(list2)# Checking conditionif out: print("True")else : print("False") |
True
Time complexity: O(n*m), where n and m are the lengths of list1 and list2 respectively.
Auxiliary space: O(1), as only a few variables are used and no additional data structures are created.
Method#4: Using intersection() method
Another approach to check if two lists have any elements in common is to use the built-in intersection function of the set class. This function returns a new set that contains the common elements of the two sets. If the intersection of the two sets is not empty, then it means that the lists have at least one element in common. Here’s an example of how this could be implemented:
Python3
# Initialization of listlist1 = [1, 2, 3, 4, 55]list2 = [2, 3, 90, 22]#Finding intersectioncommon_elements = set(list1).intersection(list2)if common_elements: print("True")else: print("False")#This code is contributed by Edula Vinay Kumar Reddy |
True
Time complexity: O(n), where n is the length of the smaller list. This is because the intersection function iterates through each element of the smaller list and checks if it is present in the other list.
Auxiliary space: O(n), because the intersection function creates a new set that contains the common elements of the two lists, which has a size equal to the number of common elements.
Method #5 : Using operator.countOf() method
Python3
import operator as op# Python code to check if two lists# have any element in common# Initialization of listlist1 = [1, 3, 4, 55]list2 = [90, 22]flag = 0# Using in to check element of# second list into first listfor elem in list2: if op.countOf(list1,elem)>0: flag = 1# checking conditionif flag == 1: print("True") else : print("False") |
False
Time Complexity: O(N)
Auxiliary Space: O(1)
Method #6: Using recursion
Step-by-step algorithm for the code:
- Define a function find_common_elements that takes in two lists list1 and list2 as arguments.
- Check if either of the lists is empty. If yes, return False.
- Check if the first element of list1 is in list2. If yes, return True.
- If the first element of list1 is not in list2, make a recursive call to the function by passing the remaining elements of list1 and list2 as arguments.
- If no common element is found after checking all the elements of list1, return False.
- Define two lists list1 and list2.
- Call the find_common_elements function with the above-defined lists.
- If the function returns True, print “True”. Else, print “False”.
End of program.
Python3
# Python code to check if two lists# have any element in commondef find_common_elements(list1, list2): """ Finds if two lists have any common element Args: list1, list2: input lists Returns: True if a common element exists, else False """ # Using recursion if not list1 or not list2: return False if list1[0] in list2: return True return find_common_elements(list1[1:], list2)# Example usagelist1 = [1, 2, 3, 4, 55]list2 = [2, 3, 90, 22]if find_common_elements(list1, list2): print("True")else: print("False")#This code is contributed by vinay Pinjala. |
True
Time complexity: O(m * n) in the worst case, where m and n are the lengths of the input lists. This is because the function checks each element of the first list against each element of the second list. In the best case, when the first element of the first list matches the first element of the second list, the function returns in O(1) time.
The space complexity O(m) in the worst case, where m is the length of the longer list. This is because the function makes recursive calls with smaller lists, so at any point in time, there are at most m elements in the call stack. In the best case, when the two lists have no common elements, the function returns in O(1) space.
