[Solved] Convert Nested Dictionary into Flattened in Python

Problem Statement:

You have given a nested dictionary (dictionary inside another dictionary). Write a program to convert the nested dictionary into a nested dictionary.

Let’s take an below example.

Input Dictionary:

{  'a' : 1,
   'b' : { 
           'c': 3,
            'd': 4
    }
}

Output (Flatten) Dictionary:

{  'a' : 1,
   'b' : 2,
   'c': 3,
   'd': 4
}

Here the value of ‘b’ in output dictionary is two as there are two elements having key ‘c’ and ‘d’ in the given nested dictionary.

Elements in the nested dictionary will be added as it is in the output dictionary.

Algorithm:

• Take an empty dictionary for output (says ‘out_dict’)
• Traverse through all the elements in the dictionary.
  • If the data type of the value is ‘dict’, add a new element in the out_dict in the dictionary with the same ‘key’ and length if the nested dictionary as value. Append the nested dictionary as it is to the out_dict.
  • Else, element as it is to the out_dict.
• Print the ‘out_dict’.

Program to Convert Nested Dictionary into Flattened in Python:

We are using items() method to iterate over all the elements in the dictionary and update() method for adding one dictionary to another dictionary.

Check Python dictionary tutorial for more.

Program:

def flat_dict(sample_dict):
  out_dict = {}

  for key, val in sample_dict.items():
    if type(val) == dict:
      out_dict[key] = len(sample_dict.keys())
      out_dict.update(val)
    else:
      out_dict[key] = val

  return out_dict


if __name__ == "__main__":
  sample_dict = {'a' : 1, 'b' : {'c': 3, 'd': 4}}
  out_dict = flat_dict(sample_dict)
  print(out_dict)

Output:

{'a': 1, 'b': 2, 'c': 3, 'd': 4}

This program was asked in Juniper interview for Python developer.

Complexity:

Every element in the dictionary traversed only once. The time complexity is O(n) where n is the size of the dictionary.

We are creating a new dictionary to save the flatten dictionary. The space complexity is O(n), where n is the size of the dictionary.

Sometimes, in the interview coding round, the interviewer may ask you to solve this problem without creating any extras space. In that case, you can modify the given dictionary instead of creating a new one. The space complexity will become O(1).

This is all about a program to convert nested dictionary into flattened in Python. Also, check other coding interview questions for practicing and improving your programming skills.