Python | Check if two lists have at-least one element common

Given two lists a, b. Check if two lists have at least one element common in them. 

Examples:

Input : a = [1, 2, 3, 4, 5]
        b = [5, 6, 7, 8, 9]
Output : True

Input : a=[1, 2, 3, 4, 5]
        b=[6, 7, 8, 9]
Output : False

Method 1: Traversal of List

Using traversal in two lists, we can check if there exists one common element at least in them. While traversing two lists if we find one element to be common in them, then we return true. After complete traversal and checking, if no elements are same, then we return false. 

Output:

True 
False

Time complexity: O(n*m), where n and m are the lengths of the input lists.
Auxiliary space: O(1).

Method 2 : Using Set and Property

Using set’s and property, if there exists at least one common element then set(a)&set(b) returns a positive integer, if it does not contains any positive integer, then it returns 0. So we insert a in set_a and b in set_b and then check if set_a & set_b for a positive integer or not. 

Output:

True 
False

Time complexity: O(m + n), where m and n are the lengths of the input lists a and b, respectively.
Auxiliary space: O(m + n), for creating the two sets a_set and b_set.

Method 3 : Using Set Intersection

Using set’s intersection inbuilt function. a_set.intersection(b_set) returns a positive integer if there is at least one element in common, else it returns 0. So we insert a in set_a and b in set_b and then check a_set.intersection(b_set), and returns depending on the value. 

Output:

True 
False

Time complexity: O(n), where n is the size of the larger list between a and b. 
Auxiliary space: O(n), where n is the size of the larger list between a and b.

Another approach that can be used to check if two lists have at least one common element is to use the Counter class from the collections module. The Counter class is a subclass of dict that is used to count the occurrences of elements in a list.

Here is an example of how the Counter class can be used to check if two lists have at least one common element:

True
False

Time complexity: O(n+m), where n is the length of list1 and m is the length of list2.

Auxiliary space: O(k), where k is the number of unique elements in both lists combined. 

Method #5 : Using operator.countOf() method

True

Time Complexity: O(N)
Auxiliary Space: O(1)

Method 4: Using the any() function and the list comprehension method.

This methos uses the any() function along with list comprehension to check if two lists have at least one common element. The list comprehension creates a list of boolean values by comparing each element of the first list to each element of the second list. The any() function returns True if at least one of the boolean values in the list is True, indicating that there is at least one common element between the two lists.

Algorithm:

Create a boolean list using list comprehension that compares each element of the first list to each element of the second list.
Check if any() of the boolean values in the list is True.
If any() is True, return True. Otherwise, return False.

True
False

Time complexity: O(n*m), where n and m are the lengths of the input lists.
Auxiliary space: O(1).