Problem

Write a function to flatten a nested dictionary. Namespace the keys with a period.

Examples

Example 1

1
2
3

Input: {"key": 3, "foo": {"a": 5, "bar": {"baz": 8}}}
Output: {"key": 3, "foo.a": 5, "foo.bar.baz": 8}
Explanation: The nested dictionary "foo", which contains "a" and "bar", and "bar" itself contains "baz", is flattened using a dot (.) to namespace the keys.

Example 2

1
2
3

Input: {"a": 1, "b": {"c": 2, "d": {"e": 3}}}
Output: {"a": 1, "b.c": 2, "b.d.e": 3}
Explanation: The nested dictionary "b", which contains "c" and "d", and "d" itself contains "e", is flattened using a dot (.) to namespace the keys.

Solution

Method 1 - Recursion

To flatten a nested dictionary, we need to recursively traverse the dictionary and concatenate the keys as we delve deeper into the nested structure.

Approach

  1. Initial Setup: Create a helper function to recursively flatten the dictionary.
  2. Recursive Traversal: Traverse the dictionary keys, and if the value is another dictionary, call the helper function recursively with the updated key.
  3. Concatenation: Concatenate keys with a dot to namespace them appropriately.
  4. Base Case: If the key’s value is not a dictionary, add it to the output dictionary.
  5. Combine Results: Collect all the flattened keys and values in the resultant dictionary.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Solution {
    public Map<String, Object> flatten(Map<String, Object> dict) {
        Map<String, Object> ans = new HashMap<>();
        flattenHelper("", dict, ans);
        return ans;
    }

    private void flattenHelper(String prefix, Map<String, Object> dict, Map<String, Object> ans) {
        for (Map.Entry<String, Object> entry : dict.entrySet()) {
            String key = entry.getKey();
            Object value = entry.getValue();
            String newKey = prefix.isEmpty() ? key : prefix + "." + key;

            if (value instanceof Map) {
                flattenHelper(newKey, (Map) value, ans);
            } else {
                ans.put(newKey, value);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Map<String, Object> input = new HashMap<>();
        Map<String, Object> foo = new HashMap<>();
        Map<String, Object> bar = new HashMap<>();
        bar.put("baz", 8);
        foo.put("a", 5);
        foo.put("bar", bar);
        input.put("key", 3);
        input.put("foo", foo);

        Map<String, Object> result = solution.flatten(input);
        System.out.println(result);  // Output: {key=3, foo.a=5, foo.bar.baz=8}
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def flatten(self, dict_: Dict[str, Any]) -> Dict[str, Any]:
        ans: Dict[str, Any] = {}
        self.flatten_helper("", dict_, ans)
        return ans

    def flatten_helper(self, prefix: str, current: Dict[str, Any], ans: Dict[str, Any]) -> None:
        for key, value in current.items():
            new_key = f"{prefix}.{key}" if prefix else key
            if isinstance(value, dict):
                self.flatten_helper(new_key, value, ans)
            else:
                ans[new_key] = value

# Example usage
sol = Solution()
input_dict = {
    "key": 3,
    "foo": {
        "a": 5,
        "bar": {
            "baz": 8
        }
    }
}
result = sol.flatten(input_dict)
print(result)  # Output: {'key': 3, 'foo.a': 5, 'foo.bar.baz': 8}

Complexity

  • ⏰ Time complexity: O(n) where n is the total number of keys in the dictionary.
  • 🧺 Space complexity: O(n) to store the flattened dictionary.