Given a dictionary, extract items from a particular level.
Examples:
Input : {“Gfg” : { “n1”: 3, “nd2”: { “n2” : 6 }}, “is” : { “ne1”: 5, “ndi2”: { “ne2” : 8, “ne22” : 10 } }}, K = 2
Output : {‘n2’: 6, ‘ne2’: 8, ‘ne22’: 10}
Explanation : 2nd nesting items are extracted.Input : {“Gfg” : { “n1”: 3, “nd2”: { “n2” : 6 }}, “is” : { “ne1”: 5, “ndi2”: { “ne2” : 8, “ne22” : 10 } }}, K = 1
Output : {“n1”: 3, “ne1”: 5}
Explanation : Elements of 1st nesting extracted.
Method #1 : Using isinstance() + recursion
This is one of the ways in which this task can be performed. In this, we perform required recursion for inner nestings, and isinstance is used to differentiate between dict instance and other data types to test for nesting.
Python3
# Python3 code to demonstrate working of# Get particular Nested level Items from Dictionary# Using isinstance() + recursion# helper functiondef get_items(test_dict, lvl): # querying for lowest level if lvl == 0: yield from ((key, val) for key, val in test_dict.items() if not isinstance(val, dict)) else: # recur for inner dictionaries yield from ((key1, val1) for val in test_dict.values() if isinstance(val, dict) for key1, val1 in get_items(val, lvl - 1))# initializing dictionarytest_dict = {"Gfg": { "n1": 3, "nd2": { "n2": 6 }}, "is": { "ne1": 5, "ndi2": { "ne2": 8, "ne22": 10 } }}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# initializing KK = 2# calling functionres = get_items(test_dict, K)# printing resultprint("Required items : " + str(dict(res))) |
The original dictionary is : {‘Gfg’: {‘n1’: 3, ‘nd2’: {‘n2’: 6}}, ‘is’: {‘ne1’: 5, ‘ndi2’: {‘ne2’: 8, ‘ne22’: 10}}} Required items : {‘n2’: 6, ‘ne2’: 8, ‘ne22’: 10}
Method #2: Using Stack :
Step by step Algorithm :
- Define a function ‘get_items’ that takes two inputs test_dict and lvl and creates a list named ‘stack’ and appends a tuple of test_dict and lvl.
- Create an empty list named ‘items’.
- Start a while loop until stack is not empty and inside the loop, pop the last element from the stack and store it in current_dict and current_lvl variables.
- Start a for loop for items of the current_dict.
- Check if the value of the item is a dictionary or not.
a) If it is not a dictionary, then check if the current_lvl is 0.
b) If current_lvl is 0, then append the tuple of key and value in the items list.
c) If it is a dictionary, then check if the current_lvl is greater than 0.
d) If it is greater than 0, then append the tuple of the value and current_lvl-1 in the stack list. - Return the items list.
- Print the original dictionary and K.
- Call the ‘get_items’ function with test_dict and K as input and store the result in res.
- Print the required items.
Python3
def get_items(test_dict, lvl): stack = [(test_dict, lvl)] items = [] while stack: current_dict, current_lvl = stack.pop() for key, val in current_dict.items(): if type(val) != dict: if current_lvl == 0: items.append((key, val)) else: if current_lvl > 0: stack.append((val, current_lvl - 1)) return itemstest_dict = {"Gfg": { "n1": 3, "nd2": { "n2": 6 }}, "is": { "ne1": 5, "ndi2": { "ne2": 8, "ne22": 10 } }}print("The original dictionary is : " + str(test_dict))K = 2res = get_items(test_dict, K)print("Required items : " + str(dict(res))) |
The original dictionary is : {'Gfg': {'n1': 3, 'nd2': {'n2': 6}}, 'is': {'ne1': 5, 'ndi2': {'ne2': 8, 'ne22': 10}}}
Required items : {'ne2': 8, 'ne22': 10, 'n2': 6}
Complexity Analysis :
Time complexity: O(n)
The time complexity of this code is O(n), where n is the total number of items in the dictionary. This is because It visits each item only once.
Space complexity: O(m)
The space complexity of this algorithm is O(m), where m is the maximum depth of the nested dictionary. This is because it uses a stack to store the nested dictionaries.
