Given a dictionary with a values list, extract the key whose value has the most unique values.
Input : test_dict = {"Gfg" : [5, 7, 9, 4, 0], "is" : [6, 7, 4, 3, 3], "Best" : [9, 9, 6, 5, 5]}
Output : "Gfg"
Explanation : "Gfg" having max unique elements i.e 5.
Input : test_dict = {"Gfg" : [5, 7, 7, 7, 7], "is" : [6, 7, 7, 7], "Best" : [9, 9, 6, 5, 5]}
Output : "Best"
Explanation : 3 (max) unique elements, 9, 6, 5 of "Best".
Method #1: Using loop
This is a brute way in which this task can be performed. In this, we iterate for all the list values and check for each key’s value count, extracting the key with maximum unique values.
Python3
# Python3 code to demonstrate working of# Key with maximum unique values# Using loop# initializing dictionarytest_dict = {"Gfg": [5, 7, 5, 4, 5], "is": [6, 7, 4, 3, 3], "Best": [9, 9, 6, 5, 5]}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))max_val = 0max_key = Nonefor sub in test_dict: # Testing for length using len() method and # converted to set for duplicates removal if len(set(test_dict[sub])) > max_val: max_val = len(set(test_dict[sub])) max_key = sub# Printing resultprint("Key with maximum unique values : " + str(max_key)) |
The original dictionary is : {‘Gfg’: [5, 7, 5, 4, 5], ‘is’: [6, 7, 4, 3, 3], ‘Best’: [9, 9, 6, 5, 5]} Key with maximum unique values : is
Time complexity: O(n*k*log k), where n is the number of keys in the dictionary and k is the length of the largest list among all the lists in the dictionary. This is because the program iterates through each key in the dictionary, and for each key, it first creates a set from the list associated with that key (which takes O(k) time) and then finds the length of the set (which takes O(klog k) time due to the sorting operation in the set). Therefore, the total time complexity is O(nk*log k).
Auxiliary space: O(k), because the program creates a set for each list in the dictionary, and the size of each set can be at most k (if all the elements in the list are distinct).
Method #2: Using sorted() + lambda() + set() + values() + len()
The combination of the above functions can be used to solve this problem. In this, we reverse sort the dictionary keys on basis of set length and return the first result.
Python3
# Python3 code to demonstrate working of # Key with maximum unique values# Using sorted() + lambda() + set() + values() + len()# Initializing dictionarytest_dict = {"Gfg" : [5, 7, 5, 4, 5], "is" : [6, 7, 4, 3, 3], "Best" : [9, 9, 6, 5, 5]}# Printing original dictionaryprint("The original dictionary is : " + str(test_dict))# Sorting to reverse sort dictionarymax_key = sorted(test_dict, key = lambda ele: len( set(test_dict[ele])), reverse = True)[0]# Printing result print("Key with maximum unique values : " + str(max_key)) |
The original dictionary is : {‘Gfg’: [5, 7, 5, 4, 5], ‘is’: [6, 7, 4, 3, 3], ‘Best’: [9, 9, 6, 5, 5]} Key with maximum unique values : is
Time complexity: O(NlogN), where N is the number of keys in the dictionary.
Auxiliary space: O(N), where N is the number of keys in the dictionary.
Method #3:Using Counter() method
Python3
# Python3 code to demonstrate working of# Key with maximum unique valuesfrom collections import Counter# initializing dictionarytest_dict = {"Gfg": [5, 7, 5, 4, 5], "is": [6, 7, 4, 3, 3], "Best": [9, 9, 6, 5, 5]}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))max_val = 0max_key = Nonefor sub in test_dict: # test for length using len() # converted to Counter() to calculcate the unique values # (for duplicates removal) if len(Counter(test_dict[sub])) > max_val: max_val = len(set(test_dict[sub])) max_key = sub# printing resultprint("Key with maximum unique values : " + str(max_key)) |
The original dictionary is : {'Gfg': [5, 7, 5, 4, 5], 'is': [6, 7, 4, 3, 3], 'Best': [9, 9, 6, 5, 5]}
Key with maximum unique values : is
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Method #4: Using a list comprehension:
Algorithm:
- Initialize a dictionary named “test_dict” with keys “Gfg”, “is”, and “Best”, and corresponding values as lists of integers.
- Print the original dictionary.
- Use a list comprehension to create a list of tuples “unique_counts”, where each tuple contains a key-value pair
- from the dictionary and the number of unique values in the corresponding list.
- Use the max() function with a key argument to find the tuple with the maximum unique value.
- Extract the key from the tuple with the maximum unique value.
- Print the key with the maximum unique value.
Python3
# Initializing dictionarytest_dict = {"Gfg": [5, 7, 5, 4, 5], "is": [6, 7, 4, 3, 3], "Best": [9, 9, 6, 5, 5]}# Printing the original dictionaryprint("The original dictionary is : " + str(test_dict))# Creating a list of tuples# where each tuple contains the key and# the number of unique values# using list comprehensionunique_counts = [(key, len(set(values))) for key, values in test_dict.items()]# Finding the key with the maximum unique values# using the max() function with a key argumentmax_key = max(unique_counts, key=lambda x: x[1])[0]# Printing the resultprint("Key with maximum unique values : " + str(max_key))# This code is contributed by Rayudu |
The original dictionary is : {'Gfg': [5, 7, 5, 4, 5], 'is': [6, 7, 4, 3, 3], 'Best': [9, 9, 6, 5, 5]}
Key with maximum unique values : is
Time complexity: O(n), where n is the total number of values in the dictionary. This is because we need to iterate over all the values in the dictionary to compute the number of unique values for each key.
Auxiliary Space: O(n), where n is the total number of values in the dictionary. This is because we need to store all the key-value pairs in the dictionary as well as the list of tuples “unique_counts”.
Method #5: Using defaultdict and set
- Import defaultdict from the collections module.
- Create an empty defaultdict with the default value set to an empty set.
- Loop through the values in the dictionary.
- For each value, loop through the elements in the list and add them to the set for the corresponding key in the defaultdict.
- Loop through the keys in the dictionary and find the key with the maximum length of the set of unique values.
- Print the result.
Python3
from collections import defaultdict# Initializing dictionarytest_dict = {"Gfg": [5, 7, 5, 4, 5], "is": [6, 7, 4, 3, 3], "Best": [9, 9, 6, 5, 5]}# Creating defaultdict with default value set to an empty setunique_vals = defaultdict(set)# Looping through values and add elements to sets in defaultdictfor key, value in test_dict.items(): # Iterating element in value for elem in value: unique_vals[key].add(elem)# Finding key with maximum length of unique valuesmax_key = max(unique_vals, key=lambda x: len(unique_vals[x]))# Printing the resultprint("Key with maximum unique values : " + str(max_key)) |
Key with maximum unique values : is
Time complexity: O(nm), where n is the number of keys in the dictionary and m is the maximum length of the lists in the dictionary.
Auxiliary space: O(nm), where n is the number of keys in the dictionary and m is the maximum length of the lists in the dictionary.
Method #6: Using dictionary comprehension and set
Stepwise Approach:
- Initialize a dictionary comprehension that iterates over the key-value pairs of the original dictionary.
- For each key-value pair, create a new key-value pair where the key is the original key, and the value is a set of the unique elements in the original value list.
- Use the max() function with a key argument to find the key with the maximum number of unique elements in its corresponding value set.
- Print the result.
Python3
# Initializing dictionarytest_dict = {"Gfg": [5, 7, 5, 4, 5], "is": [6, 7, 4, 3, 3], "Best": [9, 9, 6, 5, 5]}# Printing the original dictionaryprint("The original dictionary is : " + str(test_dict))# create a dictionary where each key is the original key,# and each value is a set of the unique elements in the original value list# using a dictionary comprehension unique_dict = {key: set(values) for key, values in test_dict.items()}# using the max() function with a key argument to# find the key with the maximum number of unique elements in its corresponding value setmax_key = max(unique_dict, key=lambda x: len(unique_dict[x]))# Printing the resultprint("Key with maximum unique values : " + str(max_key)) |
The original dictionary is : {'Gfg': [5, 7, 5, 4, 5], 'is': [6, 7, 4, 3, 3], 'Best': [9, 9, 6, 5, 5]}
Key with maximum unique values : is
Time complexity: O(n logn) due to the use of the max() function with a key argument, which requires sorting.
Auxiliary space: O(n) due to the creation of a new dictionary.
