# Flatten a Dictionary

Given 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).

`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`

.

`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)`

.