Flatten a Dictionary
MediumGiven a dictionary dict, write a function flattenDictionary that returns a flattened version of it. Assume that values are either an integer, a string, or another dictionary.
If a certain key is empty, it should be excluded from the output (see e in the example below).
Example
input: dict = { "Key1" : "1", "Key2" : { "a" : "2", "b" : "3", "c" : { "d" : "3", "e" : { "" : "1" } } } } output: { "Key1" : "1", "Key2.a" : "2", "Key2.b" : "3", "Key2.c.d" : "3", "Key2.c.e" : "1" }
Important: when you concatenate keys, make sure to add the dot character between them. For instance, when concatenating Key2, c, and d the resulting key would be Key2.c.d.
Recursion is a natural choice for this kind of problem. We iterate over the keys in dict and distinguish between two cases: If the value mapped to a key is a primitive, we take that key and simply concatenate it to the flattened key we've created up to this point. We then map the resulting key to the value in the output dictionary. If the value is a dictionary, we again concatenate the keys, but instead of adding the resulting key and value to the output dictionary, we recurse on the value with the newly formed key.
Because it is useful to create the output dictionary outside of the recursive function, it makes sense to use a helper function in this problem.
Pseudocode:
function flattenDictionary(dict): flatDictionary = {} flattenDictionaryHelper("", dict, flatDictionary) return flatDictionary function flattenDictionaryHelper(initialKey, dict, flatDictionary): for (key : dict.keyset()): value = dict.get(key) if (!isDictionary(value)): # the value is of a primitive type if (initialKey == null || initialKey == ""): flatDictionary.put(key, value) else: flatDictionary.put(initialKey + "." + key, value) else: if (initialKey == null || initialKey == "") flattenDictionaryHelper(key, value, flatDictionary) else: flattenDictionaryHelper(initialKey + "." + key, value, flatDictionary)
Time Complexity: O(N), where N is the number of keys in the input dictionary. We visit every key in the dictionary only once, hence the linear time complexity.
Space Complexity: O(N) since the output dictionary is asymptotically as big as the input dictionary. We also store recursive calls in the execution stack which in the worst-case scenario could be O(N), as well. The total is still O(N).