Given a flattened dictionary, the task is to convert that dictionary into a nested dictionary where keys are needed to be split at ‘_’ considering where nested dictionary will be started.
Method #1: Using Naive Approach
Step-by-step approach :
- Define a function named insert that takes two parameters, a dictionary (dct) and a list (lst). This function iterates over all elements of the input list except the last two elements, and creates nested dictionaries corresponding to each element in the list.
- The insert() function then updates the dictionary (dct) with a key-value pair where the key is the second last element of the input list, and the value is the last element of the input list.
- Define a function named convert_nested that takes a dictionary (dct) as an input. This function first initializes an empty dictionary named result to store the output nested dictionary.
- The function then creates an iterator named lists, which is a list of lists where each list represents a hierarchical flow of keys and values from the input dictionary. To create this iterator, it splits each key of the input dictionary by the ‘_’ character and appends the corresponding value to the list.
- The convert_nested() function then iterates over each list in the lists iterator and inserts it into the result dictionary using the insert() function.
- Finally, the convert_nested() function returns the resulting nested dictionary result.
- Define an initial dictionary named ini_dict containing key-value pairs.
- Print the initial dictionary using the print() function.
- Create a new list named _split_dict that contains lists representing the hierarchical flow of keys and values from the initial dictionary by splitting each key of the dictionary by the ‘_’ character and appending the corresponding value to the list.
- Print the final nested dictionary by calling the convert_nested() function on the initial dictionary and print the resulting nested dictionary using the print() function.
Below is the implementation of the above approach:
Python3
# Python code to demonstrate# conversion of flattened dictionary# into nested dictionarydef insert(dct, lst): for x in lst[:-2]: dct[x] = dct = dct.get(x, dict()) dct.update({lst[-2]: lst[-1]}) def convert_nested(dct): # empty dict to store the result result = dict() # create an iterator of lists # representing nested or hierarchical flow lists = ([*k.split("_"), v] for k, v in dct.items()) # insert each list into the result for lst in lists: insert(result, lst) return result # initialising_dictionaryini_dict = {'Geeks_for_for':1,'Geeks_for_Lazyroar':4, 'for_Lazyroar_Geeks':3,'Lazyroar_Geeks_for':7}# printing initial dictionaryprint ("initial_dictionary", str(ini_dict))# code to convert ini_dict to nested # dictionary splitting_dict_keys_split_dict = [[*a.split('_'), b] for a, b in ini_dict.items()]# printing final dictionaryprint ("final_dictionary", str(convert_nested(ini_dict))) |
Output
initial_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}
final_dictionary {'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Lazyroar': {'Geeks': {'for': 7}}}
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using default dict and recursive approach
Python3
# Python code to demonstrate# conversion of flattened dictionary# into nested dictionary# code to convert dict into nested dictdef nest_dict(dict1): result = {} for k, v in dict1.items(): # for each key call method split_rec which # will split keys to form recursively # nested dictionary split_rec(k, v, result) return resultdef split_rec(k, v, out): # splitting keys in dict # calling_recursively to break items on '_' k, *rest = k.split('_', 1) if rest: split_rec(rest[0], v, out.setdefault(k, {})) else: out[k] = v # initialising_dictionaryini_dict = {'Geeks_for_for':1,'Geeks_for_Lazyroar':4, 'for_Lazyroar_Geeks':3,'Lazyroar_Geeks_for':7}# printing initial dictionaryprint ("initial_dictionary", str(ini_dict))# printing final dictionaryprint ("final_dictionary", str(nest_dict(ini_dict))) |
Output
initial_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}
final_dictionary {'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Lazyroar': {'Geeks': {'for': 7}}}
Time complexity: O(n), where n is the length of the key string.
Auxiliary space: O(N * n), where N is the number of items in the input dictionary and n is the length of the longest key string.
Method #3: Using reduce and getitem
Python3
# Python code to demonstrate# conversion of flattened dictionary# into nested dictionaryfrom collections import defaultdictfrom functools import reducefrom operator import getitemdef getFromDict(dataDict, mapList): # Iterate nested dictionary return reduce(getitem, mapList, dataDict) # instantiate nested defaultdict of defaultdictstree = lambda: defaultdict(tree)d = tree()# converting default_dict_to regular dictdef default_to_regular(d): """Convert nested defaultdict to regular dict of dicts.""" if isinstance(d, defaultdict): d = {k: default_to_regular(v) for k, v in d.items()} return d # initialising_dictionaryini_dict = {'Geeks_for_for':1,'Geeks_for_Lazyroar':4, 'for_Lazyroar_Geeks':3,'Lazyroar_Geeks_for':7}# printing initial dictionaryprint ("initial_dictionary", str(ini_dict))# code to convert ini_dict to nested dictionary# iterating_over_dictfor k, v in ini_dict.items(): # splitting keys * keys, final_key = k.split('_') getFromDict(d, keys)[final_key] = v# printing final dictionaryprint ("final_dictionary", str(default_to_regular(d))) |
Output
initial_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}
final_dictionary {'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Lazyroar': {'Geeks': {'for': 7}}}
Time complexity: O(n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(nm), where n and m are the same as explained above
Method 4 : Using a recursive function without defaultdict or reduce
uses a recursive function add_to_nested_dict to add values to a nested dictionary. The function takes a nested dictionary, a list of keys, and a value as inputs. If the list of keys has only one key, the function adds the value to the nested dictionary at that key. Otherwise, it creates a nested dictionary at the first key if it doesn’t already exist, and then recursively calls the function with the remaining keys and value.
step-by-step approach :
- Create a function add_to_nested_dict that takes three arguments: a nested dictionary, a list of keys, and a value. This function will add the value to the nested dictionary at the specified keys.
- Check if the length of the keys list is 1. If it is, add the value to the nested dictionary at the last key in the list.
- If the length of the keys list is greater than 1, check if the first key is in the nested dictionary. If it isn’t, create a new nested dictionary at that key.
- Recursively call the add_to_nested_dict function with the nested dictionary at the first key in the list, the remaining keys in the list, and the value.
- Create an empty dictionary d that will hold the nested dictionary.
- Iterate over the flattened dictionary ini_dict using a for loop.
- Split each key in ini_dict into a list of keys using the split method.
- Call the add_to_nested_dict function with the empty dictionary d, the list of keys, and the value.
- Print the final nested dictionary d.
Python3
def add_to_nested_dict(nested_dict, keys, value): """Add a value to a nested dictionary at the specified keys.""" if len(keys) == 1: # base case: add value to the last key in the list nested_dict[keys[0]] = value else: # recursive case: create nested dictionary if it doesn't exist if keys[0] not in nested_dict: nested_dict[keys[0]] = {} # recursively call function with remaining keys and value add_to_nested_dict(nested_dict[keys[0]], keys[1:], value)# initialising_dictionaryini_dict = {'Geeks_for_for':1,'Geeks_for_Lazyroar':4, 'for_Lazyroar_Geeks':3,'Lazyroar_Geeks_for':7}# printing initial dictionaryprint ("initial_dictionary", str(ini_dict))# create empty nested dictionaryd = {}# iterating_over_dictfor k, v in ini_dict.items(): # splitting keys keys = k.split('_') # add value to nested dictionary add_to_nested_dict(d, keys, v)# printing final dictionaryprint ("final_dictionary", str(d)) |
Output
initial_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}
final_dictionary {'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Lazyroar': {'Geeks': {'for': 7}}}
The time complexity of this approach is O(nm), where n is the number of keys in the flattened dictionary and m is the maximum depth of the nested dictionary.
The auxiliary space is also O(nm), since the function creates nested dictionaries as needed.
Method 5: Using a loop to iterate through the list of keys
- Create an empty dictionary.
- Iterate through the items in the initial dictionary using a for loop.
- Split the keys into a list using the split() method and store the value in a variable.
- Create a variable temp that references the empty dictionary.
- Iterate through the list of keys using a for loop.
- If the key exists in temp, update temp to reference the value of that key.
- If the key does not exist in temp, create a new key with an empty dictionary as its value and update temp to reference that value.
- When the loop through the keys is finished, set the final value of the last key in the list to be the value from the initial dictionary.
- Return the nested dictionary.
Python3
def add_to_nested_dict(nested_dict, keys, value): """Add a value to a nested dictionary at the specified keys.""" temp = nested_dict for key in keys[:-1]: temp = temp.setdefault(key, {}) temp[keys[-1]] = value return nested_dict# initialising_dictionaryini_dict = {'Geeks_for_for':1,'Geeks_for_Lazyroar':4, 'for_Lazyroar_Geeks':3,'Lazyroar_Geeks_for':7}# printing initial dictionaryprint ("initial_dictionary", str(ini_dict))# create empty nested dictionaryd = {}# iterating_over_dictfor k, v in ini_dict.items(): # splitting keys keys = k.split('_') # add value to nested dictionary add_to_nested_dict(d, keys, v)# printing final dictionaryprint ("final_dictionary", str(d)) |
Output
initial_dictionary {'Geeks_for_for': 1, 'Geeks_for_Lazyroar': 4, 'for_Lazyroar_Geeks': 3, 'Lazyroar_Geeks_for': 7}
final_dictionary {'Geeks': {'for': {'for': 1, 'Lazyroar': 4}}, 'for': {'Lazyroar': {'Geeks': 3}}, 'Lazyroar': {'Geeks': {'for': 7}}}
Time complexity: O(n*m), where n is the number of items in the initial dictionary and m is the maximum number of keys in a single item.
Auxiliary space: O(m), where m is the maximum number of keys in a single item.
