Python Program to extract dictionaries with maximum number of keys

Given a list of dictionaries, the task is to write a Python program to extract a dictionary with a maximum number of keys.

Input : test_list = [{'Gfg' : 1}, {'Gfg' : 1, 'is' : 5, 'best' : 4}, {'Gfg' : 2, 'best' : 9}]
Output : {'Gfg' : 1, 'is' : 5, 'best' : 4}
Explanation : Dictionary with max. length 3 is output.

Input : test_list = [{'Gfg' : 1}, {'Gfg' : 2, 'best' : 9}]
Output : {'Gfg' : 2, 'best' : 9}
Explanation : Dictionary with max. length 2 is output.

Method 1 : Using len() and loop

In this, we iterate for all the dictionaries and keep track of the number of keys, comparing and updating the maximum at each step.

This method displays only the first dictionary found with a maximum number of elements i.e. if more than one dictionary has the same number of elements and this number is maximum then only the first dictionary will be displayed.

Example:

The original list is : [{'Gfg': 1}, {'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9}]
Dictionary with maximum keys  : {'Gfg': 1, 'is': 5, 'best': 4}

Time Complexity: O(n), where n is the value in dictionary.
Auxiliary Space: O(n), where n is the size of dictionary.

Method 2 : Using max() and list comprehension

In this, we get the maximum length of the number of keys present in dictionary lists. Then dictionaries with maximum length computed are extracted. This method allows multiple results for matching keys.

Example:

The original list is : [{'Gfg': 1}, {'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9, 'book': 1}]
Dictionary with maximum keys  : [{'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9, 'book': 1}]

Method 3: Using reduce() function from the functools module

Approach:

1. Import the reduce() function from the functools module: from functools import reduce
2. Initialize a lambda function that takes two dictionaries as arguments and returns the dictionary with the maximum number of keys:
3. Use the reduce() function to apply the lambda function to each pair of dictionaries in the list of dictionaries. The reduce() function returns a single dictionary with the maximum number of keys:
4. Create a new list containing only the dictionary with the maximum number of keys:
5. Print the result.

Example:

The original list is : [{'Gfg': 1}, {'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9, 'book': 1}]
Dictionary with maximum keys  : [{'Gfg': 1, 'is': 5, 'best': 4}]

Time complexity: O(n), where n is the number of dictionaries in the list. The reduce() function iterates over the list of dictionaries once.
Auxiliary space: O(1), since we only need to store the max_dict variable and the max_keys_dict lambda function.

Method 4: using the sorted() function and lambda functions. 

Steps:

1. Sort the list of dictionaries in descending order based on the number of keys in each dictionary. (We can do this using the sorted() function and a lambda function that returns the length of the dictionary.)
2. Store the result in a variable sorted_list.
3. Extract the first dictionary from the sorted list, which will be the dictionary with the maximum number of keys. You can do this using indexing and storing it in a variable max_dict.
4. Create a list with only the max_dict and store it in a variable res.
5. Print the res list to get the dictionary with the maximum keys.

The original list is : [{'Gfg': 1}, {'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9, 'book': 1}]
Dictionary with maximum keys  : [{'Gfg': 1, 'is': 5, 'best': 4}]

Time complexity: O(nlog n), where n is the number of dictionaries in the input list. The sorted() function takes O(nlog n) time.
Auxiliary space: O(n), where n is the number of dictionaries in the input list. This is because the sorted() function creates a new list with the same number of elements as the input list.

Method 5: Using len(),index(),max() methods

Steps:

1. Initiate a for loop to traverse over the list of dictionaries test_list.
2. Append the length of each dictionary to an empty list x using len() and append() methods.
3. Set result to dictionary with maximum keys using index() and max() methods.
4. Display result.

The original list is : [{'Gfg': 1}, {'Gfg': 1, 'is': 5, 'best': 4}, {'Gfg': 2, 'best': 9}]
Dictionary with maximum keys : {'Gfg': 1, 'is': 5, 'best': 4}

Time Complexity: O(N) N – length of test_list.
Auxiliary Space : O(N) N – length of dictionary res

Method 6: Using the heapq.nlargest() function.

1. First, we import the heapq module which provides functions for heap operations on lists.
2. Then, we define a list of dictionaries called test_list with three elements.
3. We use the heapq.nlargest() function to get the dictionary with maximum length. The function takes three arguments: the number of items we want to return (in this case, 1), the list we want to find the largest elements from (test_list), and a key function that determines how to compare elements. Here, we use len as the key function to compare the length of each dictionary. The function returns a list of the n largest items.
4. We access the first (and only) element of the result list using the index [0] and store it in the res variable.
5. Finally, we print the result using the print() function and concatenate the string “Dictionary with maximum keys: ” with the string representation of the res variable using the str() function.

Dictionary with maximum keys: {'Gfg': 1, 'is': 5, 'best': 4}

Time complexity: O(n log k), where n is the number of dictionaries in the input list and k is the number of dictionaries to be returned. .
Auxiliary space: O(k), where k is the number of dictionaries to be returned. In this case, k is 1, so the auxiliary space is O(1).