Sometimes, while working with Python dictionaries, we can have a problem in which we need to convert the nested list values to individual records to include another level of nesting to accommodate data. This kind of problem can have applications in data domains such as web development and Machine Learning. Let’s discuss certain ways in which this task can be performed.
Input : test_dict = {‘gfg’ : [4, 5], ‘best’ : [8, 10, 7, 9]}
Output : {‘best’: [{8: []}, {10: []}, {7: []}, {9: []}], ‘gfg’: [{4: []}, {5: []}]}Input : test_dict = {‘gfg’ : [7]}
Output : {‘gfg’: [{7: []}]}
Method #1 : Using loop + enumerate() The combination of above functions can be used to solve this problem. This is brute force approach to this in which we iterate for all list and create records list for each value.
Python3
# Python3 code to demonstrate working of # Convert Value list elements to List records# Using loop + enumerate()# initializing dictionarytest_dict = {'gfg' : [4, 5], 'is' : [8], 'best' : [10]}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Convert Value list elements to List records# Using loop + enumerate()for ele in test_dict.values(): for idx, val in enumerate(ele): ele[idx] = {val: []}# printing result print("The converted dictionary is : " + str(test_dict)) |
The original dictionary : {‘best’: [10], ‘is’: [8], ‘gfg’: [4, 5]} The converted dictionary is : {‘best’: [{10: []}], ‘is’: [{8: []}], ‘gfg’: [{4: []}, {5: []}]}
Time complexity: O(n*m) where n is the number of keys in the dictionary and m is the maximum length of the value lists.
Auxiliary space: O(1) as the conversion is done in-place, and no additional data structures are created.
Method #2 : Using dictionary comprehension + items() This is shorthand method to solve this problem. In this, the dictionary is created using dictionary comprehension and dictionary items are extracted using items().
Python3
# Python3 code to demonstrate working of # Convert Value list elements to List records# Using dictionary comprehension + items()# initializing dictionarytest_dict = {'gfg' : [4, 5], 'is' : [8], 'best' : [10]}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Convert Value list elements to List records# Using dictionary comprehension + items()res = {key: [{val: []} for val in sub] for key, sub in test_dict.items()}# printing result print("The converted dictionary is : " + str(res)) |
The original dictionary : {‘best’: [10], ‘is’: [8], ‘gfg’: [4, 5]} The converted dictionary is : {‘best’: [{10: []}], ‘is’: [{8: []}], ‘gfg’: [{4: []}, {5: []}]}
The time complexity of this code is O(n*m), where n is the number of keys in the test_dict dictionary and m is the length of the longest list value in the dictionary.
The space complexity of this code is O(n*m), where n is the number of keys in the test_dict dictionary and m is the length of the longest list value in the dictionary.
Method#3: Using Recursive method.
Algorithm:
- Start by iterating over the keys of the input dictionary, d.
- For each key, check if the value is a list. If it is, create a new empty list, new_list.
- For each element in the original list, check if it is a dictionary. If it is, append it to the new_list.
- If the element is not a dictionary, create a new dictionary with the element as the key and an empty list as the value, and append the dictionary to the new_list.
- Replace the original list value with the new list value in the dictionary.
- If the value is a dictionary, call the convert_to_list_records() function recursively on the value.
- Return the modified dictionary.
Python3
def convert_to_list_records(d): for key in d: if isinstance(d[key], list): new_list = [] for element in d[key]: if isinstance(element, dict): new_list.append(element) else: new_list.append({element: []}) d[key] = new_list elif isinstance(d[key], dict): convert_to_list_records(d[key]) return d# initializing dictionarytest_dict = {'gfg' : [4, 5], 'is' : [8], 'best' : [10]}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# Convert Value list elements to List records# Using dictionary comprehension + items()res = convert_to_list_records(test_dict)# printing resultprint("The converted dictionary is : " + str(res))#this code contributed by tvsk |
The original dictionary : {'gfg': [4, 5], 'is': [8], 'best': [10]}
The converted dictionary is : {'gfg': [{4: []}, {5: []}], 'is': [{8: []}], 'best': [{10: []}]}
Time complexity:
The time complexity of the function is O(n), where n is the total number of elements in the input dictionary. This is because the function visits every element in the dictionary once, either to check its type or to modify it. Since each element is visited once, the time complexity is linear in the size of the input.
Auxiliary space:
The auxiliary space complexity of the function is O(m), where m is the total number of elements in the input dictionary that are converted to a list of dictionary records. This is because the function creates a new list for each list value in the input dictionary, and may create additional dictionaries as well. The maximum number of new dictionaries that can be created is equal to the number of non-dictionary elements in the input dictionary. Therefore, the space complexity of the function is also linear in the size of the input.
Method #4: Using Queue and BFS (Breadth-First Search)
Define a function convert_to_list_records_BFS(d) that takes a dictionary d as input and returns the modified dictionary.
Initialize an empty queue queue and add the dictionary d to the queue.
While the queue is not empty, pop the first element from the queue and iterate over its keys.
For each key, if the corresponding value is a list, create a new empty list new_list.
Iterate over each element in the list, and if it is a dictionary, add it to the new_list, else add a new dictionary with the element as key and an empty list as value to the new_list.
Replace the original value of the key with the new list.
If the value is a dictionary, add it to the queue.
Return the modified dictionary.
Python3
from collections import dequedef convert_to_list_records_BFS(d): queue = deque([d]) while queue: cur_dict = queue.popleft() for key in cur_dict.keys(): if isinstance(cur_dict[key], list): new_list = [] for element in cur_dict[key]: if isinstance(element, dict): new_list.append(element) else: new_list.append({element: []}) cur_dict[key] = new_list elif isinstance(cur_dict[key], dict): queue.append(cur_dict[key]) return dtest_dict = {'gfg' : [4, 5], 'is' : [8], 'best' : [10]}print("The original dictionary : " + str(test_dict))convert_to_list_records_BFS(test_dict)print("The converted dictionary is : " + str(test_dict)) |
The original dictionary : {'gfg': [4, 5], 'is': [8], 'best': [10]}
The converted dictionary is : {'gfg': [{4: []}, {5: []}], 'is': [{8: []}], 'best': [{10: []}]}
Time complexity: O(n), where n is the total number of elements in the dictionary and its nested dictionaries.
Auxiliary space: O(n), where n is the total number of elements in the dictionary and its nested dictionaries.
