Given a Matrix, perform merge on the basis of the element in the first column.
Input : test_list = [[4, “neveropen”], [3, “Gfg”], [4, “CS”], [4, “cs”], [3, “best”]]
Output : [[4, ‘neveropen’, ‘CS’, ‘cs’], [3, ‘Gfg’, ‘best’]]
Explanation : 4 is paired withneveropen, CS and cs hence are merged into 1 row.Input : test_list = [[4, “neveropen”], [3, “Gfg”], [4, “CS”], [5, “cs”], [3, “best”]]
Output : [[4, ‘neveropen’, ‘CS’, ‘cs’], [3, ‘Gfg’, ‘best’], [5, ‘cs’]]
Explanation : 4 is paired withneveropen and CS hence are merged into 1 row.
Method 1 : Using setdefault() and list comprehension
In this, the task of grouping is done using setdefault(), which assigns key as first column element and rest of elements as values of list. List comprehension is used post that to get all the values from the dictionary constructed.
Python3
# Initializing listtest_list = [[4, "neveropen"], [3, "Gfg"], [4, "CS"], [4, "cs"], [3, "best"]]# Printing original listprint("The original list is : " + str(test_list))res = {}for key, val in test_list: # Merging similar values using setdefault() res.setdefault(key, []).append(val)# Getting all valuesres = [[key] + val for key, val in res.items()]# Printing resultprint("Merged Matrix : " + str(res)) |
Output:
The original list is : [[4, ‘neveropen’], [3, ‘Gfg’], [4, ‘CS’], [4, ‘cs’], [3, ‘best’]] Merged Matrix : [[4, ‘neveropen’, ‘CS’, ‘cs’], [3, ‘Gfg’, ‘best’]]
Time Complexity: O(m*n) where m and n is the number of rows and columns respectively in the list “test_list”. T
Auxiliary Space: O(k) additional space of size k is created
Method 2 : Using values() and setdefault()
Here, we extract the values using values(), rest all the operations are performed in a similar manner as explained above. This program omits from the list the first column element based on which grouping was performed.
Python3
# Initializing listtest_list = [[4, "neveropen"], [3, "Gfg"], [4, "CS"], [4, "cs"], [3, "best"]]# Printing original listprint("The original list is : " + str(test_list))res = {}for key, val in test_list: # setdefault used to merge similar values res.setdefault(key, []).append(val)# fetch values using value()res = list(res.values())# Printing resultprint("Merged Matrix : " + str(res)) |
Output:
The original list is : [[4, ‘neveropen’], [3, ‘Gfg’], [4, ‘CS’], [4, ‘cs’], [3, ‘best’]] Merged Matrix : [[‘neveropen’, ‘CS’, ‘cs’], [‘Gfg’, ‘best’]]
Method 3: Using defaultdict and for loop
Use defaultdict from the collections module, which automatically initializes any new keys with the default value specified (in this case, an empty list). Then, iterate over the list of lists and append the second element of each list to the list corresponding to the first element (key) in the dictionary. Finally, combine the key and values into a new list of lists.
Approach:
- Initialize a list of lists containing key-value pairs.
- Create an empty dictionary to store the merged results.
- Iterate over the list of lists and for each key-value pair:
a. If the key already exists in the dictionary, append the value to the corresponding list.
b. If the key does not exist in the dictionary, create a new list with the value and add it to the dictionary with the key as the key. - Combine the key and values for each dictionary item into a new list of lists.
- Print the final merged list.
Follow the below steps to implement the above idea:
Python3
from collections import defaultdict# Initializing listtest_list = [[4, "neveropen"], [3, "Gfg"], [4, "CS"], [4, "cs"], [3, "best"]]# Printing original listprint("The original list is : " + str(test_list))res = defaultdict(list)for key, val in test_list: res[key].append(val)# Getting all valuesres = [[key] + val for key, val in res.items()]# Printing resultprint("Merged Matrix : " + str(res)) |
The original list is : [[4, 'neveropen'], [3, 'Gfg'], [4, 'CS'], [4, 'cs'], [3, 'best']] Merged Matrix : [[4, 'neveropen', 'CS', 'cs'], [3, 'Gfg', 'best']]
Time complexity: O(n), where n is the length of the input list. This is because we iterate over the list of lists only once.
Auxiliary space: O(n), where n is the length of the input list. This is because we create a dictionary with at most n keys and values, and the final merged list also has at most n elements.
Method 4: Using itertools.groupby() function
Python3
from itertools import groupby# initializing listtest_list = [[4, "neveropen"], [3, "Gfg"], [4, "CS"], [4, "cs"], [3, "best"]]# sorting the list by the first element of each sublisttest_list.sort(key=lambda x: x[0])# using groupby() to group the sublists by the first elementgrouped = groupby(test_list, key=lambda x: x[0])# creating a dictionary with the first element of each sublist as the key and# a list of the second elements as the valueres = {key: [val[1] for val in vals] for key, vals in grouped}# printing resultprint("Merged Matrix : " + str(res)) |
Merged Matrix : {3: ['Gfg', 'best'], 4: ['neveropen', 'CS', 'cs']}
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, since we need to store the sorted list and the dictionary.
