Python – Filter Key from Nested item

Sometimes, while working with Python dictionaries, we can have a problem in which we need to extract the keys which have a particular key-value pair as part of their nested item. This kind of problem is common in web development domain. Lets discuss certain ways in which this task can be performed.

Input : test_dict = {‘gfg’ : {‘best’ : 10, ‘good’ : 5}} 
Output : [‘gfg’] 

Input : test_dict = {‘gfg’ : {‘best’ : 10, ‘good’ : 12}} 
Output : []

Method #1: Using loop + __contains__ The combination of above functions constitutes the brute force way to perform this task. In this, we iterate for each key using loop and check for value presence using __contains__. 

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time complexity: O(N*M), where N is the number of items in the test_dict and M is the number of keys in the que_dict.
Auxiliary Space: O(K), where K is the number of matched keys. This is because we are storing the matched keys in the res list.

Method #2: Using dictionary comprehension + get() The combination of above functions provide another way to solve this problem. In this, we perform the check of element presence using get(). 

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time complexity: O(N*M), where N is the number of items in the test_dict and M is the number of keys in the que_dict.
Auxiliary Space: O(K), where K is the number of matched keys. This is because we are storing the matched keys in the res list.

Method 3: Using simple for loop

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time Complexity: O(n), where n is the number of keys in the dictionary.
Auxiliary Space: O(1)

Method #4: Using List Comprehension

This method uses a list comprehension to iterate through the dictionary items and checks if the nested dictionary contains the key “good” with a value of 5, as specified in the que_dict. If so, it appends the outer key to a list comprehension.

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time complexity: O(n), where n is the number of items in the test_dict. This is because the list comprehension iterates through all the items in test_dict once.
Auxiliary space: O(k), where k is the number of matches found. This is because it creates a list to store the matching keys. In the worst case, where all items in test_dict contain the key “good” with a value of 5, the space complexity would be O(n). However, in most cases, the number of matches would be smaller than the number of items in test_dict.

Method #5: Using the built-in filter() function with a lambda function

This approach uses the filter() function to create a new iterable that only contains the keys that meet the specified conditions. The lambda function checks if the key’s nested item contains the specified key and if its value is equal to the value in the que_dict.

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time complexity: O(n), where n is the number of items in the dictionary
Auxiliary space: O(k), where k is the number of matching keys.

Method #6: Using recursion

• Initialize the dictionary test_dict with the given key-value pairs.
• Print the original dictionary using the print() function.
• Initialize the dictionary que_dict with the key ‘good’ and the value 5.
• Define a recursive function filter_dict() that takes in a dictionary and a query dictionary and returns a list of keys from the original dictionary that meet the filtering condition.
• In the function, iterate through the items in the dictionary, and if the value is another dictionary, recursively call the function on that nested dictionary.
• If the nested dictionary contains the key ‘good’ and its value is equal to the value in the query dictionary, add the key to the result list.
• Return the result list.
• Call the filter_dict() function with the test_dict and que_dict dictionaries to get the matching keys.
• Print the resulting list of keys using the print() function.

The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}, 'Maths': {'good': 5}}
Match keys : ['gfg', 'Maths']

Time complexity: O(n), where n is the total number of key-value pairs in all the nested dictionaries.
Auxiliary space: O(h), where h is the maximum depth of the nested dictionaries.