Python | Merge two list of lists according to first element

Given two list of lists of equal length, write a Python program to merge the given two lists, according to the first common element of each sublist. 

Examples:

Input : lst1 = [[1, 'Alice'], [2, 'Bob'], [3, 'Cara']]
        lst2 = [[1, 'Delhi'], [2, 'Mumbai'], [3, 'Chennai']]
Output : [[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Input : lst1 = [ ['c', 'class'], ['g', 'greek'], ]
        lst2 = [['c', 'coder'], ['g', 'god'], ]
Output : [['c', 'class', 'coder'], ['g', 'greek', 'god']]

Method #1: Python zip() with list comprehension 

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Time complexity: O(n), where n is the number of elements in the lists.
Auxiliary space: O(n), as a new list is created with the combined elements from both lists.

Method #2 : Python enumerate() with list comprehension 

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Time complexity: O(n), where n is the length of lst1 or lst2 (whichever is smaller), as we are iterating through the lists only once.
Auxiliary space: O(n), where n is the length of lst1 or lst2 (whichever is smaller), as we are creating a new list of the same length.

Method #3: Python dictionary In this method, we initialize ‘dict1’ with collections.defaultdict and traverse through ‘lst1’+’lst2’ and append the first element of ‘lst1’ as key and tupled second element of both respective sublists as value. Finally, we traverse through ‘dict1’ and initialize ‘dictlist’ with the desired output. 

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Time complexity: O(n), where n is the total number of elements in lst1 and lst2. 
Auxiliary space: O(n), where n is the total number of elements in lst1 and lst2.

Method #4: Using extend() and for loop

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Time Complexity: O(n), where n is the length of the list test_list 
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list 

Method #5: Using a list comprehension and a dictionary comprehension ( 2 lines ):

In the first line of the function, we initialize a dictionary called values with the values from the second list. We do this by using a dictionary comprehension, which is a concise way to create a dictionary from an iterable. The comprehension iterates through each sublist in lst2 and stores the first element as the key and the second element as the value.

In the second line, we use a list comprehension to iterate through each sublist in lst1 and merge it with the corresponding values in values. The comprehension checks if the first element of the sublist is in values using the in keyword. If it is, it creates a new list with the first element of the sublist, the second element of the sublist, and the value from values that corresponds to the first element. If the first element is not in values, the sublist is not included in the merged list.

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Tme complexity: O(n), where n is the length of the lists, since we are iterating through both lists once.
Auxiliary space: O(n), since we are storing the values from the second list in a dictionary.

Method #6: Using a for loop and a dictionary

Step-by-step approach:

• Create an empty dictionary merged_dict
• Traverse through the lists lst1 and lst2 using a for loop
• For each iteration, get the first element of the sublist and check if it already exists as a key in the merged_dict
• If it does not exist, create a new key with the first element of the sublist as the key and the second element as the value in a list format
• If it does exist, append the second element of the current sublist to the list associated with the existing key
• After the for loop, create a list merged_list that will contain the merged sublists based on the keys in the merged_dict
• Traverse through the keys in the merged_dict and append a new list to merged_list with the current key and the associated list of values
• Return the merged_list as the final output

Below is the implementation of the above approach:

[[1, 'Alice', 'Delhi'], [2, 'Bob', 'Mumbai'], [3, 'Cara', 'Chennai']]

Time complexity: O(n), where n is the length of the input lists
Auxiliary space: O(n), where n is the length of the input lists, for creating the dictionary and merged list