Dictionaries in Python is same as Associative arrays or Maps in other languages. Unlike lists, dictionaries stores data in key-value pair.
Let’s see how to find the second maximum value in a Python dictionary.
Method #1: Naive Approach:
A general approach is to find the largest value of the dictionary and then iterate over the dictionary maintaining the value that must be greater than all the other values and less than the maximum value.
Python3
# Python naive approach to find the # second largest element in a dictionary# creating a new dictionarynew_dict ={"google":12, "amazon":9, "flipkart":4, "gfg":13}# maximum valuemax = max(new_dict.values())# iterate through the dictionarymax2 = 0for v in new_dict.values(): if(v>max2 and v<max): max2 = v# print the second largest valueprint(max2) |
12
Method #2: Using sorted() method
We can find the second largest value in a dictionary by sorting the values of the dictionaries and then retrieving the second last element from the sorted list.
Python3
# Python code to find second largest# element from a dictionary using sorted() method# creating a new Dictionaryexample_dict = {"mark": 13, "steve": 3, "bill": 6, "linus": 11}# now directly print the second largest# value in the dictionaryprint("Output1:", sorted(example_dict.values())[-2])# More than 1 keys with maximum value are presentexample_dict = {"fb": 20, "whatsapp": 12, "instagram": 20, "oculus": 10}print("Output2:", sorted(set(example_dict.values()), reverse=True)[-2]) |
Output1: 11 Output2: 12
Time complexity: O(nLogn)
Auxiliary Space: O(1)
Explanation: example_dict.values() gives list of all the values in the dictionary. sorted() method will sort the list of dict_values. list(sorted(example_dict.values()))[-2] converts dict_values to list and return the second last element of the sorted list, i.e. the second largest value of dictionary.
if more than one maximum values are present in the dictionary as shown in the 2nd example, converting the dictionary values to a set will eliminate the duplicates.
Method #3: Using heap
Another approach to find the second maximum value in a dictionary is to use the heap data structure. Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This structure allows us to easily find the maximum element in the heap.
To find the second maximum value in a dictionary, we can use a heap to store the values of the dictionary, and then repeatedly extract the maximum element until we find the second maximum value.
Here is an example of how this can be implemented using the heapq module in Python:
Python3
import heapq# creating a new Dictionaryexample_dict = {"mark": 13, "steve": 3, "bill": 6, "linus": 11}# Find the second maximum value in the dictionary using heapqsecond_max = heapq.nlargest(2, example_dict.values())[1]print(second_max) # Output: 11#This code is contributed by Edula Vinay Kumar Reddy |
11
The time complexity of this approach is O(n*log(n)), where n is the number of elements in the dictionary. The space complexity is O(n), as we need to store all the values of the dictionary in the heap. If more than one similar value is there then convert to set then heapify.
