Python program to find the key of maximum value tuples in a dictionary

Given a dictionary with values as tuples, the task is to write a python program to find the key of maximum value tuples. 

Examples:

Input : test_dict = {‘gfg’ : (“a”, 3), ‘is’ : (“c”, 9), ‘best’ : (“k”, 10), ‘for’ : (“p”, 11), ‘Lazyroar’ : (‘m’, 2)}
Output : for
Explanation : 11 is maximum value of tuple and for key “for”.

Input : test_dict = {‘gfg’ : (“a”, 13), ‘is’ : (“c”, 9), ‘best’ : (“k”, 10), ‘for’ : (“p”, 1), ‘Lazyroar’ : (‘m’, 2)}
Output : gfg
Explanation : 13 is maximum value of tuple and for key “gfg”.

Method #1 : Using max() + values() + next()

In this, the maximum of all the tuple values are found using max(), and values are extracted using values(). The next(), is used for iteration using the iterator method of access, and each tuple value is compared with the maximum value. 

The original dictionary is : {'gfg': ('a', 3), 'is': ('c', 9), 'best': ('k', 10), 'for': ('p', 11), 'Lazyroar': ('m', 2)}
The maximum key : for

Time complexity: O(nlogn) where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(1) as only constant extra space is used for storing the variables.

Method #2 : Using list comprehension + max() + values()

In this, we perform the task of getting all the maximum matching values using list comprehension. Getting maximum is done using max().

The original dictionary is : {'gfg': ('a', 3), 'is': ('c', 9), 'best': ('k', 10), 'for': ('p', 11), 'Lazyroar': ('m', 2)}
The maximum key : for

Time complexity: O(n*logn) – where n is the number of items in the dictionary.
Auxiliary space: O(n) – as we are creating a new list to store the keys that have the maximum value.

Method #3: Using a for loop to iterate over dictionary items and comparing tuple values

Step-by-step approach:

• Initialize a variable max_val to a tuple with two elements, where the first element is an empty string and the second element is negative infinity. This variable will hold the current maximum value as we iterate over the dictionary.
• Initialize a variable res to an empty string. This variable will hold the key with the maximum value as we iterate over the dictionary.
• Iterate over the dictionary using a for loop that loops over the items in the dictionary.
  • For each item, use an if statement to compare the second element of the tuple value to the second element of the max_val variable. If the current tuple value has a greater second element, update max_val to the current tuple value and update res to the current key.
• Print the result using the print() function.

Below is the implementation of the above approach:

The original dictionary is : {'gfg': ('a', 3), 'is': ('c', 9), 'best': ('k', 10), 'for': ('p', 11), 'Lazyroar': ('m', 2)}
The maximum key : for

Time complexity: O(n), where n is the number of items in the dictionary. 
Auxiliary space: O(1), as we are only using a constant amount of memory to store the max_val and res variables.

Method #4: Using the sorted() function with a lambda function

Step-by-step approach:

• Initialize the dictionary.
• Use the sorted() function with a lambda function to sort the dictionary items based on the second element of the tuple values.
• Get the last item (i.e., the item with the highest second element) from the sorted dictionary.
• Extract the key from the item.
• Print the key.

Below is the implementation of the above approach:

The original dictionary is : {'gfg': ('a', 3), 'is': ('c', 9), 'best': ('k', 10), 'for': ('p', 11), 'Lazyroar': ('m', 2)}
The maximum key : for

Time complexity: O(nlogn) due to the sorting operation.
Auxiliary space: O(n) for the sorted list.

Method #5: Using the reduce() function from functools module

Explanation:

1. We first import the reduce() function from the functools module.
2. We initialize the dictionary as before.
3. The reduce() function takes a function as its first argument and an iterable (in this case, the dictionary keys) as its second argument. The function is applied cumulatively to the items of the iterable from left to right. Here, we use a lambda function that compares the values associated with the keys and returns the key with the maximum value.
4. Finally, we print the key with maximum value.

The original dictionary is : {'gfg': ('a', 3), 'is': ('c', 9), 'best': ('k', 10), 'for': ('p', 11), 'Lazyroar': ('m', 2)}
The maximum key : for

Time Complexity: The time complexity of this method is O(n), where n is the number of items in the dictionary. 

Auxiliary Space: The space complexity of this method is O(1), as we are only storing the key with maximum value and not creating any new data structures.