Python – Key with maximum unique values

Last Updated : 15 May, 2023

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 dictionary
test_dict = {"Gfg": [5, 7, 5, 4, 5],
             "is": [6, 7, 4, 3, 3],
             "Best": [9, 9, 6, 5, 5]}
 
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
 
max_val = 0
max_key = None
 
for 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 result
print("Key with maximum unique values : " + str(max_key))

Output

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 dictionary
test_dict = {"Gfg" : [5, 7, 5, 4, 5],
             "is" : [6, 7, 4, 3, 3], 
             "Best" : [9, 9, 6, 5, 5]}
 
# Printing original dictionary
print("The original dictionary is : " + str(test_dict))
 
# Sorting to reverse sort dictionary
max_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))

Output

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 values
from collections import Counter
 
# initializing dictionary
test_dict = {"Gfg": [5, 7, 5, 4, 5],
             "is": [6, 7, 4, 3, 3],
             "Best": [9, 9, 6, 5, 5]}
 
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
 
max_val = 0
max_key = None
 
for 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 result
print("Key with maximum unique values : " + str(max_key))

Output

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 dictionary
test_dict = {"Gfg": [5, 7, 5, 4, 5],
             "is": [6, 7, 4, 3, 3],
             "Best": [9, 9, 6, 5, 5]}
 
# Printing the original dictionary
print("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 comprehension
unique_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 argument
max_key = max(unique_counts, key=lambda x: x[1])[0]
 
# Printing the result
print("Key with maximum unique values : " + str(max_key))
 
# This code is contributed by Rayudu

Output

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 dictionary
test_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 set
unique_vals = defaultdict(set)
 
# Looping through values and add elements to sets in defaultdict
for 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 values
max_key = max(unique_vals, key=lambda x: len(unique_vals[x]))
 
# Printing the result
print("Key with maximum unique values : " + str(max_key))

Output

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 dictionary
test_dict = {"Gfg": [5, 7, 5, 4, 5],
             "is": [6, 7, 4, 3, 3],
             "Best": [9, 9, 6, 5, 5]}
 
# Printing the original dictionary
print("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 set
max_key = max(unique_dict, key=lambda x: len(unique_dict[x]))
 
# Printing the result
print("Key with maximum unique values : " + str(max_key))

Output

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.