Python – Remove K valued key from Nested Dictionary
Sometimes, while working with records, we can have a problem in which we need to perform the removal of a key from nested dictionary whose value us specific to K. This is a common problem and has its application in data domains such as web development. Lets discuss certain ways in which this task can be performed.
Input : test_dict = {‘CS’: {‘priceless’: 6}, ‘is’: {‘better’: 6}, ‘gfg’: {‘best’: 6}}
Output : {‘CS’: {}, ‘gfg’: {}, ‘is’: {}}Input : test_dict = {‘CS’: {‘priceless’: 9}, ‘is’: {‘better’: 8}, ‘gfg’: {‘best’: 7}}
Output : {‘CS’: {‘priceless’: 9}, ‘is’: {‘better’: 8}, ‘gfg’: {‘best’: 7}}
Method #1: Using loop + isinstance() + filter() The combination of above functions can be used to solve this problem. In this, we perform the task of K value using filter() and isinstance() is used to test for nesting dictionary. The dictionary construction is done using loop.
Python3
# Python3 code to demonstrate working of # Remove K valued key from Nested Dictionary # Using loop + isinstance() + filter() # initializing dictionary test_dict = { 'gfg' : { 'best' : 4 , 'good' : 5 }, 'is' : { 'better' : 6 , 'educational' : 4 }, 'CS' : { 'priceless' : 6 }} # printing original dictionary print ("The original dictionary : " + str (test_dict)) # initializing rem_val rem_val = 6 # Remove K valued key from Nested Dictionary # Using loop + isinstance() + filter() def rem_vals(ele): global rem_val key, val = ele return val ! = rem_val res = dict () for key, val in test_dict.items(): if isinstance (val, dict ): res[key] = dict ( filter (rem_vals, val.items())) else : res[key] = val # printing result print ("Dictionary after removal : " + str (res)) |
The original dictionary : {‘is’: {‘educational’: 4, ‘better’: 6}, ‘gfg’: {‘best’: 4, ‘good’: 5}, ‘CS’: {‘priceless’: 6}} Dictionary after removal : {‘is’: {‘educational’: 4}, ‘gfg’: {‘best’: 4, ‘good’: 5}, ‘CS’: {}}
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using dictionary comprehension + isinstance() + lamda The combination of above functionalities can be used to perform this task in one liner using lambda function.
Python3
# Python3 code to demonstrate working of # Remove K valued key from Nested Dictionary # Using dictionary comprehension + isinstance() + lamda # initializing dictionary test_dict = { 'gfg' : { 'best' : 4 , 'good' : 5 }, 'is' : { 'better' : 6 , 'educational' : 4 }, 'CS' : { 'priceless' : 6 }} # printing original dictionary print ("The original dictionary : " + str (test_dict)) # initializing rem_val rem_val = 6 # Remove K valued key from Nested Dictionary # Using dictionary comprehension + isinstance() + lamda fnc = lambda sub: { key1: fnc(val1) if isinstance (val1, dict ) else val1 for key1, val1 in sub.items() if val1 ! = rem_val} res = fnc(test_dict) # printing result print ("Dictionary after removal : " + str (res)) |
The original dictionary : {‘is’: {‘educational’: 4, ‘better’: 6}, ‘gfg’: {‘best’: 4, ‘good’: 5}, ‘CS’: {‘priceless’: 6}} Dictionary after removal : {‘is’: {‘educational’: 4}, ‘gfg’: {‘best’: 4, ‘good’: 5}, ‘CS’: {}}
Time complexity: O(n), where n is the total number of key-value pairs in the dictionary.
Auxiliary space: O(n), where n is the total number of key-value pairs in the dictionary.
Method #3: Using recursion and a helper function
Use a recursive function that iterates over the keys and values of the dictionary and, if a nested dictionary is found, calls the same function on it.
Python3
def remove_key_with_value(dct, value): new_dct = {} for k, v in dct.items(): if isinstance (v, dict ): new_v = remove_key_with_value(v, value) if new_v: new_dct[k] = new_v elif v ! = value: new_dct[k] = v return new_dct |
OUTPUT- Keys Ranges : {'gfg': [1, 4], 'is': [2, 7], 'best': [6, 10]}
Time complexity: O(n), where n is the total number of keys and values in the nested dictionary.
Auxiliary space: O(n), where n is the total number of keys and values in the nested dictionary.
Method 4: Using the json module
Here’s another method that involves converting the nested dictionary to a JSON string, filtering out the key-value pairs with the specified value, and then converting the JSON string back to a dictionary:
Algorithm-
- Initialize the nested dictionary and the value to remove.
- Convert the nested dictionary to a JSON string using the json.dumps() function.
- Convert the JSON string back to a dictionary using the json.loads() function and assign it to a new dictionary variable.
- For each key-value pair in the new dictionary variable:
- If the value is a dictionary, create a new dictionary with the filtered key-value pairs that do not contain the value to remove, and assign it to the current key.
- If the value is not a dictionary, simply assign it to the current key.
- Print the updated dictionary.
Python3
import json # Python3 code to demonstrate working of # Remove K valued key from Nested Dictionary # Using the json module # initializing dictionary test_dict = { 'gfg' : { 'best' : 4 , 'good' : 5 }, 'is' : { 'better' : 6 , 'educational' : 4 }, 'CS' : { 'priceless' : 6 }} # printing original dictionary print ( "The original dictionary : " + str (test_dict)) # initializing rem_val rem_val = 6 # Convert dictionary to JSON string and back to dictionary json_dict = json.loads(json.dumps(test_dict)) for key, val in json_dict.items(): if isinstance (val, dict ): json_dict[key] = {k: v for k, v in val.items() if v ! = rem_val} else : json_dict[key] = val # printing result print ( "Dictionary after removal : " + str (json_dict)) |
The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}} Dictionary after removal : {'gfg': {'best': 4, 'good': 5}, 'is': {'educational': 4}, 'CS': {}}
Time complexity: O(n). The for loop that iterates over the dictionary also has a linear time complexity of O(n).
Auxiliary space: O(n). The additional space used by the for loop is also proportional to the size of the input dictionary. Therefore, the overall space complexity is O(n).
Method #7: Using recursion and the del statement
Step-by-step approach:
- Define a recursive function that takes a dictionary as an argument.
- Iterate over the key-value pairs of the dictionary using a for loop.
- If the value of the key-value pair is equal to the target value, delete the key-value pair using the del statement.
- If the value of the key-value pair is another dictionary, call the recursive function on that dictionary.
- Return the modified dictionary.
Python3
# initializing dictionary test_dict = { 'gfg' : { 'best' : 4 , 'good' : 5 }, 'is' : { 'better' : 6 , 'educational' : 4 }, 'CS' : { 'priceless' : 6 }} # printing original dictionary print ( "The original dictionary : " + str (test_dict)) # initializing rem_val rem_val = 6 # Using recursion and the del statement def remove_value(d): for k, v in list (d.items()): if v = = rem_val: del d[k] elif isinstance (v, dict ): remove_value(v) return d res = remove_value(test_dict) # printing result print ( "Dictionary after removal : " + str (res)) |
The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}} Dictionary after removal : {'gfg': {'best': 4, 'good': 5}, 'is': {'educational': 4}, 'CS': {}}
Time complexity: O(n), where n is the number of key-value pairs in the dictionary.
Auxiliary space: O(n) as the function modifies the original dictionary in place.
Method #8:Using re
Algorithm
- Convert the dictionary to a JSON string using json.dumps().
- Define a regular expression pattern that matches a key-value pair where the value equals rem_val. The pattern should match the key (in double quotes), followed by a colon, optional whitespace, the rem_val value, optional whitespace, and an optional comma.
- Use re.sub() to remove all matches of the pattern from the JSON string.
- Convert the modified JSON string back to a dictionary using json.loads().
- Return the modified dictionary.
Python3
import json import re # initializing dictionary test_dict = { 'gfg' : { 'best' : 4 , 'good' : 5 }, 'is' : { 'better' : 6 , 'educational' : 4 }, 'CS' : { 'priceless' : 6 }} # printing original dictionary print ( "The original dictionary : " + str (test_dict)) # initializing rem_val rem_val = 6 # Using regular expressions json_str = json.dumps(test_dict) pattern = re. compile (rf '"[^"]+":\s*{rem_val}\s*,?\s*' ) json_str = pattern.sub('', json_str) res = json.loads(json_str) # printing result print ( "Dictionary after removal : " + str (res)) #This code is contributed by Vinay Pinjala. |
The original dictionary : {'gfg': {'best': 4, 'good': 5}, 'is': {'better': 6, 'educational': 4}, 'CS': {'priceless': 6}} Dictionary after removal : {'gfg': {'best': 4, 'good': 5}, 'is': {'educational': 4}, 'CS': {}}
Time complexity:
Converting the dictionary to a JSON string using json.dumps() takes O(n) time, where n is the number of items in the dictionary.
Defining the regular expression pattern takes O(1) time.
Removing matches of the pattern from the JSON string using re.sub() takes O(n) time, where n is the length of the JSON string.
Converting the modified JSON string back to a dictionary using json.loads() takes O(n) time, where n is the length of the JSON string.
Overall, the time complexity of the algorithm is O(n), where n is the number of items in the dictionary.
Space complexity:
Converting the dictionary to a JSON string using json.dumps() takes O(n) space, where n is the number of items in the dictionary.
Defining the regular expression pattern takes O(1) space.
Removing matches of the pattern from the JSON string using re.sub() creates a new string that takes O(n) space, where n is the length of the original JSON string.
Converting the modified JSON string back to a dictionary using json.loads() creates a new dictionary that takes O(n) space, where n is the number of items in the modified dictionary.
Overall, the space complexity of the algorithm is O(n), where n is the number of items in the dictionary.