Python – Filter and Double keys greater than K

Sometimes, while working with Python dictionaries, we can have the task of extracting certain keys after manipulation and filtration, both at once. This problem can be generalized for other values and operations as well. This has applications in many domains such as day-day programming and web development. Let’s discuss certain ways in which this task can be performed. 

Method #1: Using loop 

This is one way to solve this problem. In this, we adopt brute force way to extract only filtered elements and store after doubling them. 

Step by step approach :

1. First, the dictionary test_dict is initialized with key-value pairs.
2. The original dictionary is printed using the print() function and the str() method to convert the dictionary to a string.
3. The value of K is initialized to 2.
4. An empty dictionary res is initialized.
5. A for loop is used to iterate over the key-value pairs in test_dict using the items() method.
6. Within the loop, an if statement checks if the value of the current key is greater than K.
7. If the value is greater than K, the key-value pair is added to the res dictionary with the value of the current key doubled.
8. After the loop finishes, the resulting dictionary res contains only the key-value pairs from test_dict where the value is greater than K, with the values doubled.
9. The resulting filtered dictionary is printed using the print() function and the str() method to convert the dictionary to a string.

The original dictionary : {'Gfg': 4, 'is': 2, 'best': 3, 'for': 6, 'neveropen': 1}
The filtered dictionary : {'Gfg': 8, 'best': 6, 'for': 12}

Time Complexity: O(n), where n is the length of the list test_list 
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list 

Method #2: Using dictionary comprehension This is yet another way to perform this task. In this, we perform task in similar way as the above method, but in a more compact way. 

The original dictionary : {'Gfg': 4, 'is': 2, 'best': 3, 'for': 6, 'neveropen': 1}
The filtered dictionary : {'Gfg': 8, 'best': 6, 'for': 12}

Method#3: Using Recursive method
 

The original dictionary :{'Gfg': 4, 'is': 2, 'best': 3, 'for': 6, 'neveropen': 1}
The filtered dictionary: {'Gfg': 8, 'best': 6, 'for': 12}

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #4: Using filter and map function

This program filters the dictionary items where values are greater than K, doubles the values of the filtered items, and stores them in a new dictionary. It then prints the filtered dictionary.

The filtered dictionary : {'Gfg': 8, 'best': 6, 'for': 12}

Time complexity: The time complexity of this method is O(n), where n is the number of items in the dictionary.

Auxiliary space: The auxiliary space required by this method is O(k), where k is the number of items that satisfy the condition (i.e., values greater than K).

Method 5: using the collections.defaultdict class to create a new dictionary that will store the filtered and doubled key-value pairs.

Approach :

1. Import the defaultdict class from the collections module.
2. Initialize a dictionary named test_dict with some key-value pairs.
3. Initialize a variable named K with a value of 2.
4. Create a defaultdict object named res with a default value of 0.
5. Iterate over the key-value pairs of test_dict using the items() method.
6. For each key-value pair, check if the value is greater than K.
7. If the value is greater than K, add a new key-value pair to res with the key being the same as the current key and the value being twice the current value.
8. Convert the defaultdict object res to a regular dictionary using the dict() method.
9. Print the resulting dictionary.

The filtered dictionary : {'Gfg': 8, 'best': 6, 'for': 12}

Time complexity: O(N), where N is the number of key-value pairs in the dictionary.
Auxiliary space: O(N), where N is the number of key-value pairs in the dictionary. 

Method 6: Using reduce():

Algorithm:

1. First, the filter() function is used to filter out key-value pairs where the value is greater than K.
   Then, reduce() is used to convert the filtered key-value pairs into a dictionary with the key-value pairs where the value is doubled.
2. The initial value of the reduce() function is an empty dictionary {}.
3. The reduce() function takes a lambda function as the first argument that takes two arguments x and y. Here, x represents the accumulated result and y represents the current item. The lambda function merges the accumulated result (x) and the current item (y) into a dictionary using the {**x, y[0]: y[1]*2} syntax.
4. The second argument to reduce() is the filtered key-value pairs obtained from the filter() function.

The original dictionary : {'Gfg': 4, 'is': 2, 'best': 3, 'for': 6, 'neveropen': 1}
The filtered dictionary : {'Gfg': 8, 'best': 6, 'for': 12}

Time Complexity:

The filter() function has a time complexity of O(n), where n is the number of key-value pairs in the dictionary. The reduce() function has a time complexity of O(n), where n is the number of filtered key-value pairs in the dictionary. Therefore, the overall time complexity is O(n).

Space Complexity:

The filter() function returns a generator, which has a space complexity of O(1). The reduce() function accumulates the filtered key-value pairs into a dictionary, which has a space complexity of O(n), where n is the number of filtered key-value pairs in the dictionary. Therefore, the overall space complexity is O(n).