Python – Test if common values are greater than K
Sometimes, while working with Lists, we can have a problem in which we need to track common elements in list. This is quite common and we often have constructs to solve this. But sometimes, we require to consider two list as matching if they contain atleast K matching elements. Lets discuss certain ways in which this can be performed.
Method #1 : Using set() + len() The combination of above methods can be used to solve this task. In this we first convert each list into set and then use len() to check if matching elements are greater than K.
Python3
# Python3 code to demonstrate # Test if common values are greater than K # using len() + set() # Initializing lists test_list1 = [ 'Gfg' , 'is' , 'for' , 'Beginner' ] test_list2 = [ 1 , 'Gfg' , 2 , 'Beginner' ] # printing original lists print ( "The original list 1 is : " + str (test_list1)) print ( "The original list 2 is : " + str (test_list2)) # Initializing K K = 2 # Test if common values are greater than K # using len() + set() res = len ( set (test_list1) & set (test_list2)) > = K # printing result print ( "Are common elements greater than K ? : " + str (res)) |
The original list 1 is : ['Gfg', 'is', 'for', 'Beginner'] The original list 2 is : [1, 'Gfg', 2, 'Beginner'] Are common elements greater than K ? : True
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the new res list
Method #2 : Using sum() This is yet another way in which this problem can be solved. In this, we just take count of all the column elements and sum them using sum() and then check with K.
Python3
# Python3 code to demonstrate # Test if common values are greater than K # using sum() # Initializing lists test_list1 = [ 'Gfg' , 'is' , 'for' , 'Beginner' ] test_list2 = [ 1 , 'Gfg' , 2 , 'Beginner' ] # printing original lists print ( "The original list 1 is : " + str (test_list1)) print ( "The original list 2 is : " + str (test_list2)) # Initializing K K = 2 # Test if common values are greater than K # using sum() res = sum (i in test_list1 for i in test_list2) > = 2 # printing result print ( "Are common elements greater than K ? : " + str (res)) |
The original list 1 is : ['Gfg', 'is', 'for', 'Beginner'] The original list 2 is : [1, 'Gfg', 2, 'Beginner'] Are common elements greater than K ? : True
Method #3 : Using Counter() function
Python3
# Python3 code to demonstrate # Test if common values are greater than K from collections import Counter # Initializing lists test_list1 = [ 'Gfg' , 'is' , 'for' , 'Beginner' ] test_list2 = [ 1 , 'Gfg' , 2 , 'Beginner' ] # printing original lists print ( "The original list 1 is : " + str (test_list1)) print ( "The original list 2 is : " + str (test_list2)) # Initializing K K = 2 count = 0 freq = Counter(test_list2) for i in test_list1: if i in freq.keys(): count + = 1 # Test if common values are greater than K # using sum() res = count > = K # printing result print ( "Are common elements greater than K ? : " + str (res)) |
The original list 1 is : ['Gfg', 'is', 'for', 'Beginner'] The original list 2 is : [1, 'Gfg', 2, 'Beginner'] Are common elements greater than K ? : True
Time Complexity:O(N)
Auxiliary Space:O(N)
Approach 4: Using List Comprehension
Python3
#Python3 code to demonstrate #Test if common values are greater than K #Initializing lists test_list1 = [ 'Gfg' , 'is' , 'for' , 'Beginner' ] test_list2 = [ 1 , 'Gfg' , 2 , 'Beginner' ] #printing original lists print ( "The original list 1 is : " + str (test_list1)) print ( "The original list 2 is : " + str (test_list2)) #Initializing K K = 2 #Test if common values are greater than K #using List Comprehension res = sum ([ 1 for i in test_list2 if i in test_list1]) > = K #printing result print ( "Are common elements greater than K ? : " + str (res)) |
The original list 1 is : ['Gfg', 'is', 'for', 'Beginner'] The original list 2 is : [1, 'Gfg', 2, 'Beginner'] Are common elements greater than K ? : True
Time Complexity:O(N)
Auxiliary Space:O(N)
Approach 5: Using filter and lambda function:
1. Initialize test_list1 and test_list2 with given values
2. Initialize K with given value
3. Initialize an empty list called common
4. Loop through each element i in test_list2:
a. Check if i is in test_list1
b. If it is, append i to the common list
5. Check if the length of common is greater than or equal to K
6. Print the original lists and the result of the comparison
Python3
test_list1 = [ 'Gfg' , 'is' , 'for' , 'Beginner' ] test_list2 = [ 1 , 'Gfg' , 2 , 'Beginner' ] K = 2 common = list ( filter ( lambda x: x in test_list1, test_list2)) res = len (common) > = K print ( "The original list 1 is : " + str (test_list1)) print ( "The original list 2 is : " + str (test_list2)) print ( "Are common elements greater than K? : " + str (res)) #This code is contributed by Jyothi pinjala. |
The original list 1 is : ['Gfg', 'is', 'for', 'Beginner'] The original list 2 is : [1, 'Gfg', 2, 'Beginner'] Are common elements greater than K? : True
The time complexity :O(n^2), because for each element in test_list2, it checks if it’s also in test_list1, which requires looping through test_list1 for each element in test_list2. In the worst case scenario, where both lists have n elements, the algorithm will perform n^2 operations.
The space complexity : O(n), because it stores a list of common elements in memory. The size of this list is proportional to the number of common elements, which is at most n.
has context menu
Contact Us