Python | Grouping list values into dictionary

Sometimes, while working with data, we can be encountered a situation in which we have a list of lists and we need to group its 2nd index with the common initial element in lists. Let’s discuss ways in which this problem can be solved. 

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

The defaultdict can be used to initialize the group elements and the loop can be used to group the values together and conversion to a dictionary can be done using dict(). 

The original list is : [['Gfg', 1], ['Gfg', 2], ['is', 3], ['best', 4], ['is', 5]]
The grouped dictionary is :  {'Gfg': (1, 2), 'best': (4, ), 'is': (3, 5)}

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 2: Using for loops, in and not in operators

The original list is : [['Gfg', 1], ['Gfg', 2], ['is', 3], ['best', 4], ['is', 5]]
The grouped dictionary is : {'Gfg': (1, 2), 'is': (3, 5), 'best': (4,)}

Time complexity: O(N^2) because the algorithm contains two nested loops,
Auxiliary space: O(N) because the algorithm uses a list x to store the unique elements in the first column of the input list.

 Method 3: Using dictionary comprehension and setdefault()

1. Initialize an empty dictionary res then loop through each element of test_list. 
2. For each element, get the key and value using unpacking then use the setdefault() method of dictionary to get the value for the key. 
3. If the key is not present in the dictionary, it initializes an empty list as the value then append the value to this list.

Example:

The grouped dictionary is : {'Gfg': [1, 2], 'is': [3, 5], 'best': [4]}

Time complexity: O(n), where n is the number of elements in the input list. 
Auxiliary space: O(n). This is because we need to store each key-value pair of the resulting dictionary. In the worst case, if all the keys are unique, the size of the dictionary will be the same as the size of the input list. 

Method 4: Using all() function and a generator expression

1. Use the all() function along with a generator expression to check if all the values in the Kth index of the dictionary values are equal to N. 
2. The generator expression iterates over the dictionary values and checks if the Kth index of each value is equal to N. 
3. The all() function returns True if all the values returned by the generator expression are True, otherwise it returns False.

Example:

The original dictionary : {'Gfg': [1, 4, 8], 'is': [8, 4, 2], 'best': [7, 4, 9]}
Are all Kth index equal to N : True

Time complexity: O(N), where N is the total number of values in the input dictionary.
Auxiliary space: O(1), as it only uses a constant amount of extra space to store the variables K, N, and res.

Method 5: using the any() function and a list comprehension. 

Approach:

1. Initialize the dictionary test_dict with keys and values.
2. Initialize the variable K with the index of the element you want to check in each list.
3. Initialize the variable N with the value you want to check if it’s present in the Kth index of each list.
4. Use a list comprehension to iterate over the values in test_dict and check if N is present at the K-1th index of each list.
5. Use the any() function to check if at least one of the values in the list comprehension is True. If it is, then at least one of the lists has N at the Kth index.
6. Print the result.

The original dictionary : {'Gfg': [1, 4, 8], 'is': [8, 4, 2], 'best': [7, 4, 9]}
Is at least one Kth index equal to N : True

Time complexity: O(N) because we need to iterate over all the values in the dictionary.
Auxiliary space: O(1) because we only need to store the values of K, N, and res.

METHOD 6:Using itertools

APPROACH:

This code takes an input list of lists and groups its values into a dictionary with the first element of each inner list as the key and the rest of the elements as the corresponding values. It does this using the itertools.groupby() and map() functions.

ALGORITHM:

1. The itertools.groupby() function is used to group the elements of the original_list by the first element of each inner list.
2. The resulting groups are then sorted using the sorted() function to ensure that the keys in the resulting dictionary are in alphabetical order.
3. The map() function is used to create a new dictionary by iterating over each group and mapping the first element of each group as the key and the second element of each group as the value.
4. Finally, the resulting dictionary is printed to the console.

The original list is : [['Gfg', 1], ['Gfg', 2], ['is', 3], ['best', 4], ['is', 5]]
The grouped dictionary is : {'Gfg': (1, 2), 'best': (4,), 'is': (3, 5)}

Time complexity:
The time complexity of this code is O(nlogn), where n is the length of the input list. This is because the sorted() function used to sort the groups has a time complexity of O(nlogn), and the groupby() function has a time complexity of O(n).

Space complexity:
The space complexity of this code is O(n), where n is the length of the input list. This is because the groupby() function creates an iterator object that generates the groups on-the-fly, so the amount of memory used is proportional to the number of groups, which is at most the length of the input list. The resulting dictionary also takes up space proportional to the length of the input list.