Sometimes, while working with Python dictionaries, we can come across a problem in which we have a particular value, and we need to find frequency if it’s occurrence and value is atmost K. Let’s discuss certain ways in which this problem can be solved.
Method #1: Using loop This problem can be solved using naive method of loop. In this we just iterate through each key in dictionary and when a match is found, the counter is increased.
Python3
# Python3 code to demonstrate working of # Keys Frequency with Value atmost K # Using loop # Initialize dictionary test_dict = {'gfg' : 1, 'is' : 2, 'best' : 3, 'for' : 4, 'CS' : 5} # printing original dictionary print("The original dictionary : " + str(test_dict)) # Initialize value K = 3# Using loop # Keys Frequency with Value atmost K res = 0for key in test_dict: if test_dict[key] <= K: res = res + 1 # printing result print("Frequency of keys with values till K is : " + str(res)) |
The original dictionary : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
Frequency of keys with values till K is : 3
Time complexity: O(N), where N is the number of key-value pairs in the dictionary.
Auxiliary space: O(1) as it only uses a fixed amount of memory to store the dictionary and some variables.
Method #2: Using sum() + values() This can also be solved using the combination of sum() and value(). In this, sum is used to perform the summation of values filtered and values of dictionary are extracted using values().
Python3
# Python3 code to demonstrate working of # Keys Frequency with Value atmost K # Using sum() + values() # Initialize dictionary test_dict = {'gfg' : 1, 'is' : 2, 'best' : 3, 'for' : 4, 'CS' : 5} # printing original dictionary print("The original dictionary : " + str(test_dict)) # Initialize value K = 3# Using sum() + values() # Keys Frequency with Value atmost K res = sum(x <= K for x in test_dict.values()) # printing result print("Frequency of keys with values till K is : " + str(res)) |
The original dictionary : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
Frequency of keys with values till K is : 3
The time complexity of the given code is O(n), where n is the size of the input dictionary.
The auxiliary space complexity of the code is O(1), as the code only uses a few variables to store the dictionary, the value of K, and the result of the calculation.
Method #3: Using filter() + lambda
This can also be solved using filter() and lambda function. In this, we filter the values of dictionary using lambda function and then take its length to find the frequency of occurrence.
Python3
# Python3 code to demonstrate working of# Keys Frequency with Value atmost K# Using filter() + lambda# Initialize dictionarytest_dict = {'gfg' : 1, 'is' : 2, 'best' : 3, 'for' : 4, 'CS' : 5}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Initialize value K = 3# Using filter() + lambda# Keys Frequency with Value atmost Kres = len(list(filter(lambda x: x <= K, test_dict.values())))# printing result print("Frequency of keys with values till K is : " + str(res))#This code is contributed by Edula Vinay Kumar Reddy |
The original dictionary : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
Frequency of keys with values till K is : 3
Time Complexity: O(n) where n is the number of elements in the dictionary.
Auxiliary Space: O(n) as we are creating a new list of values that are filtered using filter() function.
Method #4: Using collections module
- list is created from the dictionary.
- count() method is used to count.
- Another list comprehension is used to create a list of all the keys whose corresponding value occurs at most K times.
- The length of the list is the frequency of the keys with values at most K.
Python3
from collections import Counter# initializing dictionarytest_dict = {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}# printing original dictionaryprint("The original dictionary : " + str(test_dict))k = 3# using list comprehension to get values that are at most kvalues = [v for v in test_dict.values() if v <= k]# using Counter to count the frequency of the valuesfreq_dict = Counter(values)count = sum(freq_dict.values())# printing resultprint("Frequency of keys with values till K is : " + str(count)) |
The original dictionary : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
Frequency of keys with values till K is : 3
Time Complexity: O(N) as we are iterating over the dictionary.
Auxiliary Space: O(N) as we are creating a list.
Method #5: Using dictionary comprehension
Use a dictionary comprehension to create a new dictionary containing only the key-value pairs where the value is less than or equal to k, and then finding the length of the resulting dictionary
Python3
# initializing dictionarytest_dict = {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# initialize kk = 3# using dictionary comprehension to get key-value pairs where value is at most knew_dict = {key: value for key, value in test_dict.items() if value <= k}# get count of key-value pairs in new dictionarycount = len(new_dict)# printing resultprint("Frequency of keys with values till K is : " + str(count)) |
The original dictionary : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
Frequency of keys with values till K is : 3
Time complexity: O(n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(k), where k is the number of key-value pairs in the new dictionary.
