Python – Summation of Custom nested keys in Dictionary

Given a dictionary with keys as nested dictionaries, find the sum of values of certain custom keys inside the nested dictionary.

Input : test_dict = {‘Gfg’ : {1 : 6, 5: 9, 9: 12}, ‘is’ : {1 : 9, 5: 7, 9: 2}, ‘best’ : {1 : 3, 5: 4, 9: 14}}, sum_key = [1] 
Output : 18 
Explanation : 6 + 9 + 3 = 18, only values with key 1 are summed. 

Input : test_dict = {‘Gfg’ : {1 : 6, 5: 9, 9: 12}, ‘is’ : {1 : 9, 5: 7, 9: 2}, ‘best’ : {1 : 3, 5: 4, 9: 14}}, sum_key = [5, 9] 
Output : 48 
Explanation : Keys 5, 9 are summed.

Method #1: loop

This is the brute way in which this problem can be solved. In this, we employ a loop for all the list elements and keep updating sum value from all the nested dictionaries.

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

Time complexity: O(n*m), where n is the number of keys in the dictionary and m is the number of sum keys.
Auxiliary space: O(1), as only a constant amount of extra space is used to store the sum and loop variables.

Method #2 : Using list comprehension + sum()

The combination of above functions can also be employed to solve this problem. In this, we perform the task of summation using sum() and rest logic is also encapsulated as one-liner using list comprehension.

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

The time complexity of this code is O(NM), where N is the number of inner dictionaries in test_dict and M is the length of sum_key. 

The auxiliary space of this code is O(1) because no additional data structures are being created.

METHOD 3: use the built-in function reduce() from the functools module 

we define a lambda function sum_func that takes an accumulator (acc) and a key (key) and returns the sum of the values associated with that key in each dictionary in test_dict. We use the get() method to safely access the value of the key, returning 0 if the key is not present.

The required summation : 46

The time complexity of this approach is O(N*K), where N is the number of dictionaries in test_dict and K is the number of keys in sum_key.

The auxiliary space complexity of this approach is O(1) because we are only using constant additional space for the accumulator and the lambda function.

Method #4: use the map comprehension

• The map() function is used to apply a lambda function to each element in sum_key. 
• The lambda function first loops over each dictionary in test_dict extracts the value corresponding to the key from the inner dictionary using the key k, and then returns the sum of all these values.
• The sum() function is used to find the sum of all the values extracted using the map() function. This sum is stored in the variable res.

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

Time complexity: O(N*K) where N is the number of dictionaries in test_dict and K is the number of keys in sum_key.

Space Complexity: O(1) because we are only using constant additional space.

Method #4: Using reduce() and lambda function

Step by step Algorithm:

1. Import the reduce() function from the functools module.
2. Define the dictionary test_dict containing nested keys and values.
3. Initialize a list sum_key containing keys to sum over.
4. Use the reduce() function with a lambda expression to sum over the selected keys in the dictionary.
5. Print the result.

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

Time Complexity: O(N*K) where N is the number of dictionaries in test_dict and K is the number of keys in sum_key.
Auxiliary Space: O(1) because we are only using constant additional space.

Method 5: Use a recursive function that traverses the nested dictionary.

Step-by-step approach:

• initialize a list called sum_key with the keys whose values we want to sum.
• Define a recursive function called sum_nested_keys() that takes a dictionary as input and returns the sum of the values of the required keys.
  • Inside the sum_nested_keys() function, initialize a variable called sum_val to 0.
  • Loop over the items of the dictionary using the items() method, which returns a view object of the dictionary’s (key, value) pairs.
  • For each item, check if its value is a dictionary using the isinstance() function. 
    • If it is, we recursively call the sum_nested_keys() function with the value as input and add the returned sum to sum_val.
    • If the value is not a dictionary, check if its key is in the list of required keys sum_key. If it is, we add the value to sum_val.
• After looping over all items, return the final value of sum_val.

Below is the implementation of the above approach:

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

Time Complexity: O(n) where n is the number of elements in the dictionary, since we need to traverse all elements of the dictionary once.
Auxiliary Space: O(m) where m is the maximum depth of the nested dictionary, as we are storing the call stack of the recursive function up to the maximum depth.

Method #6: Using a stack-based iterative approach

1. Initialize an empty stack and push the root dictionary onto it, along with a running total of 0.
2. While the stack is not empty, perform the following steps:
   1. pop the top dictionary off the stack.
   2. Iterate through the dictionary’s items. If an item’s key is in the list of sum keys, add its value to the running total.
   3. If an item’s value is itself a dictionary, push it onto the stack.
3. Print the running total.

Implementation:

The original dictionary is : {'Gfg': {1: 6, 5: 9, 9: 12}, 'is': {1: 9, 5: 7, 9: 2}, 'best': {1: 3, 5: 4, 9: 14}}
The required summation : 46

Time Complexity: O(N), where N is the number of items in the nested dictionary.
Auxiliary Space: O(N), for the stack.