Python – Nested Records List from Lists

Sometimes, while working with Python Data, we can have problem in which we have data incoming in different formats. In this, we can receive data as key and value in separate dictionary and we require to make values as list of records with a new key. Lets discuss certain ways in which this task can be performed. 

Method #1 : Using zip() + loop The combination of above functionalities can be used to solve this problem. In this, we perform the pairing using zip and manual intervention of adding key is done in brute way. 

Time complexity: O(n), where n is the length of the lists “test_list1” and “test_list2”. This is because we are using a for loop that iterates over the elements of “test_list1” and “test_list2”.
Auxiliary space: O(n), where n is the length of the lists “test_list1” and “test_list2”. This is because we are creating a dictionary “res” with n key-value pairs.

Method #2 : Using dictionary comprehension + zip() This is yet another way to perform this task. This is similar to above method, just a one-liner alternative of above. 

Time complexity: O(n), where n is the number of elements in the longest list (test_list1 or test_list2). This is because the code iterates through each element of both lists once and performs a constant amount of work for each element.
Auxiliary space: O(n), as a dictionary is created to store the result. The size of the dictionary is proportional to the number of elements in the longest list.

Method #3 : Using for loops

The original list 1 is : ['gfg', 'best']
The original list 2 is : [[1, 2], [3, 4]]
The constructed dictionary is : {'gfg': [{'id': 2}, {'id': 2}], 'best': [{'id': 4}, {'id': 4}]}

Time complexity: O(n^2)
Auxiliary space: O(n^2) as well, where n is the length of test_list2.

Method#4: Using Recursive method.

Algorithm:

1. Define a function construct_dict that takes in the following arguments: keys, values, key_idx, value_idx, and add_key.
2. Initialize an empty dictionary, d with the key as keys[key_idx] and an empty list as its value.
3. For each element in values[value_idx], create a dictionary with add_key as its key and the element as its value, and append this dictionary to the value list of d.
4. Recursively call the construct_dict function with key_idx and value_idx incremented by 1 and store the returned dictionary in next_d.
5. Merge next_d with d using the update() method.
6. Return the dictionary d.
7. Call the construct_dict function with the given lists test_list1 and test_list2, and the add_key value of ‘id’.
8. Print the resulting dictionary.

The original list 1 is : ['gfg', 'best']
The original list 2 is : [[1, 2], [3, 4]]
The constructed dictionary is : {'gfg': [{'id': 1}, {'id': 2}], 'best': [{'id': 3}, {'id': 4}]}

Time complexity:
The time complexity of this algorithm is O(n*m), where n is the length of the keys list and m is the length of the values list. This is because the function iterates through each element in values and keys, and performs constant time operations for each element.

Auxiliary space complexity:
The auxiliary space complexity of this algorithm is O(n*m), where n is the length of the keys list and m is the length of the values list. This is because the function creates a new dictionary for each element in values, and each dictionary contains a single key-value pair. Additionally, the function also creates a new dictionary for each recursive call.

Method #6: Using itertools.product() and dict()

Step-by-step approach:

• First, the two lists test_list1 and test_list2 are initialized with some data.
• The original lists are displayed using the print() statement.
• The add_key variable is initialized with the string ‘id‘.
• The itertools.product() method is called with the two lists as arguments to create a Cartesian product of the two lists.
• The result of itertools.product() is then passed to the dict() method to create a dictionary from the resulting list of tuples.
• The resulting dictionary is then passed to a dictionary comprehension to group the records by the first element of each tuple.
• Finally, the resulting nested dictionary is printed to the console. 

Below is the implementation of the above approach:

The original list 1 is : ['gfg', 'best']
The original list 2 is : [[1, 2], [3, 4]]
The constructed dictionary is : {'gfg': [{'id': 3}, {'id': 4}], 'best': [{'id': 3}, {'id': 4}]}

Time complexity: O(n^2), where n is the length of the longest list value in the dictionary, due to the Cartesian product operation. 
Auxiliary Space: O(n^2)