Python – Dictionary items in value range

Given a range of values, extract all the items whose keys lie in a range of values.

Input : {‘Gfg’ : 6, ‘is’ : 7, ‘best’ : 9, ‘for’ : 8, ‘Lazyroar’ : 11}, i, j = 9, 12
Output : {‘best’ : 9, ‘Lazyroar’ : 11} 
Explanation : Keys within 9 and 11 range extracted. 

Input : {‘Gfg’ : 6, ‘is’ : 7, ‘best’ : 9, ‘for’ : 8, ‘Lazyroar’ : 11}, i, j = 14, 18 
Output : {} 
Explanation : No values in range.

Method #1: Using loop 

This is brute way in which this task can be performed. In this, we run a loop for all the keys with conditional checks for range of values.  

The original dictionary is : {'Gfg': 6, 'is': 7, 'best': 9, 'for': 8, 'Lazyroar': 11}
The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

Time complexity: O(n), where n is the number of items in the dictionary. The for loop performs the range check on each item in the dictionary, which takes O(1) time, and the overall time complexity is O(n).
Auxiliary Space: O(m), where m is the number of items in the filtered dictionary. The filtered items are stored in a new dictionary (res), so the space complexity is proportional to the size of the filtered dictionary.

Method #2 : Using filter() + lambda + dictionary comprehension 

The combination of above functions can be used to solve this problem. In this, we perform task of filtering using filter() and lambda is used for conditional checks.

The original dictionary is : {'Gfg': 6, 'is': 7, 'best': 9, 'for': 8, 'Lazyroar': 11}
The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

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

Method #3 : Using range(),keys() methods

The original dictionary is : {'Gfg': 6, 'is': 7, 'best': 9, 'for': 8, 'Lazyroar': 11}
The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

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

Method 4: Using list comprehension and dict() constructor:

The original dictionary is : {'Gfg': 6, 'is': 7, 'best': 9, 'for': 8, 'Lazyroar': 11}
The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

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

Method #5: Using dictionary comprehension with conditionals

Use a dictionary comprehension with a conditional statement to filter items from the original dictionary that fall within the specified range. The resulting dictionary is assigned to the variable res, which is printed to the console.

The original dictionary is : {'Gfg': 6, 'is': 7, 'best': 9, 'for': 8, 'Lazyroar': 11}
The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

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

Method #6: Using the items() method and list comprehension

 using the items() method and a list comprehension. The input dictionary is first initialized, and then the range is set. The list comprehension is then used to iterate over each key-value pair in the dictionary, and only the pairs where the value falls within the specified range are added to the resulting dictionary. Finally, the resulting dictionary is printed to the console.

Initialize the input dictionary.
Set the range of values to extract from the dictionary.
Use the items() method to iterate over each key-value pair in the dictionary.
Within the iteration, use a list comprehension to check whether the value falls within the specified range.
If the value falls within the specified range, add the key-value pair to the resulting dictionary.
Once all key-value pairs have been checked, the resulting dictionary will contain only the key-value pairs where the value falls within the specified range.
Print the resulting dictionary to the console.

The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

time complexity of this method is O(n), where n is the number of items in the input dictionary, since we are iterating over all items in the dictionary. The auxiliary space complexity is also O(k), where k is the number of items in the resulting dictionary, since we are creating a new dictionary to store the extracted key-value pairs.

Method#7: Using Recursive method.

Algorithm:

1. Define a recursive function, extract_dict_within_range, that takes three parameters: the input dictionary test_dict, and
2. the lower and upper bounds of the range i and j, respectively.
3. Check for the base case:
4. If test_dict is empty or i is greater than j, return an empty dictionary.
5. Initialize an empty dictionary, extracted_dict, to store the extracted items within the given range.
6. Iterate through the key-value pairs of test_dict using a for loop.
7. For each key-value pair, check if the value val is within the range [i, j] using val in range(i, j+1).
8. If the value is within the range, add the key-value pair to extracted_dict.
9. If the value is a nested dictionary, recursively call extract_dict_within_range on that nested dictionary with the same range [i, j], and update the value in extracted_dict with the result.
10. After iterating through all the key-value pairs in test_dict, return extracted_dict.

The extracted dictionary : {'best': 9, 'for': 8, 'Lazyroar': 11}

The time complexity of the recursive method depends on the size and structure of the input dictionary test_dict, as well as the range [i, j]. In the worst case, where all items in test_dict need to be checked and all values are nested dictionaries, the time complexity would be O(NM), where N is the total number of key-value pairs in test_dict, and M is the maximum depth of nested dictionaries. 

The correct space complexity for the given recursive method is O(N), where N is the total number of key-value pairs in the input dictionary test_dict.