Python – Value nested grouping on List

Sometimes, while working with data, we can have a problem in which we have flat data in the form of a list of dictionaries, and we need to perform the categorization from that bare dictionaries according to ids. This can have applications in domains that involve data, such as web development and Data Science. Let’s discuss the certain way in which this task can be performed. 

Method 1: Using defaultdict() + setdefault() + loop

The combination of the above functionalities can be used to perform this task. It is brute way in which this can be performed. In this, we initialize the defaultdict() with dictionary values for nested records formation and according to populate the data using setdefault() and conditions.

Time complexity: O(n), where n is the number of elements in the input list.
Auxiliary space: O(n), where n is the number of elements in the input list

Method 2:  “List Grouping with itertools.groupby()”

Use the groupby function to group the list of dictionaries by the ‘tag‘ key. If the ‘tag’ key is present, it creates a nested dictionary with the ‘value‘ key as the value. If the ‘tag‘ key is not present, it creates a dictionary with the ‘value‘ key as the key and an empty dictionary as the value.

Output:

The original list is : [{'value': 'Fruit'}, {'tag': 'Fruit', 'value': 'mango'}, {'value': 'Car'}, {'tag': 'Car', 'value': 'maruti'}, {'tag': 'Fruit', 'value': 'orange'}, {'tag': 'Car', 'value': 'city'}]
The dictionary after grouping : {'Fruit': {'mango', 'orange'}, 'Car': {'city', 'maruti'}}

Time complexity: O(n log n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.

Method 3- Using dictionary comprehension and iterating over the list.

The dictionary after grouping : {'Fruit': {'value': {'mango', 'orange'}}, 'Car': {'value': {'maruti', 'city'}}}

Note: In this method, if the ‘tag’ key is not present in the dictionary, the ‘value’ key with an empty set is added to the corresponding key in the resultant dictionary.

Time complexity: O(n)b where n is the length of the input list. 
Auxiliary space: O(m), where m is the number of unique ‘tag’ and ‘value’ keys in the input list.

Method 4: Using pandas library

Pandas is a popular library for data manipulation and analysis, which includes powerful tools for grouping and aggregating data.

Output:

The dictionary after grouping : {‘Car’: {‘city’, ‘maruti’}, ‘Fruit’: {‘orange’, ‘mango’}}

Time complexity: O(n log n)
Auxiliary Space: O(n + m)

Method 6: Using the collections module’s defaultdict() and a for loop to group the values based on the ‘tag’ key.

The program groups the values in the input list based on the ‘tag’ key using a defaultdict with set as the default value. It then converts the defaultdict to a regular dictionary and prints the result.

The dictionary after grouping : {'Fruit': {'mango', 'orange'}, 'Car': {'city', 'maruti'}}

Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.

Method 6: Using a list comprehension and a lambda function

1. Create a lambda function that takes an item from the input list and returns a tuple containing the ‘tag’ value (or None if ‘tag’ key is not present) and the ‘value’ value.
2. Use the lambda function inside a list comprehension to extract the tuples from the input list.
3. Use the itertools.groupby() function to group the tuples based on the ‘tag’ value.
4. Use dictionary comprehension to convert the groups into a dictionary, where the keys are the ‘tag’ values and the values are lists of the corresponding ‘value’ values.

The dictionary after grouping: {'Fruit': {'value': {'mango', 'orange'}}, 'Car': {'value': {'city', 'maruti'}}, 'mango': {}, 'maruti': {}, 'orange': {}, 'city': {}}

Time complexity: O(n log n), due to the use of itertools.groupby() function.
Auxiliary space: O(n), for the list of tuples grouped_tuples and the dictionary result_dict.