Python | Check if one dictionary is subset of other

Sometimes, while working with Python, we might have a problem in which we need to find, if a particular dictionary is part of another i.e it is a subset of another. A problem that has a huge potential in the web development domain, having knowledge of solving can be useful. Let’s discuss certain ways in which this task can be performed. 

Method #1: Using all() + items() 

This task can be performed using the combination of the above two functions, in which we check for all the items of the subdict with the original dict using all() and fetch it’s each pair using items(). 

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1 ? : True

Time complexity: O(n), where n is the number of key-value pairs in the smaller dictionary (test_dict2).
Auxiliary space: O(1), as the only additional memory used is for the boolean result (res) and the loop variables (key and val),

Method #2: Using items() + <= operator Another alternative to perform the above task can be using the items() along with the <= operator. This just checks for less than or all values of all the key values matched. 

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1 ? : True

Time complexity: O(n), where n is the number of elements in the smaller dictionary.

Auxiliary space: O(1). The memory usage is constant since the dictionaries are not being converted to any other data structure.

Method #3 : Using set() + issubset()

This is yet another approach to solve the task, in which we perform the task using set() and issubset(). The set() converts the dictionary into a set, and then issubset() checks for all the values of the subset.

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1 ? : True

Time complexity: O(n)
Auxiliary Space: O(1)

Method#4: Using the Recursive method

Algorithm:

1. Define a function is_subset_dict that takes in two dictionaries dict1 and dict2.
2. Check if the length of dict2 is greater than the length of dict1. If so, return False and terminate the function.
3. Iterate over each key-value pair in dict2.
4. Check if the key exists in dict1 and if the value is the same in both dictionaries. If not, return False and terminate the function.
5. If the function has not terminated, return True, indicating that dict2 is a subset of dict1.
6. Initialize two dictionaries test_dict1 and test_dict2.
7. Call the is_subset_dict function with the two dictionaries as arguments.
8. If the returned value is True, print a message indicating that dict2 is a subset of dict1. Otherwise, print a message indicating that it is not a subset.

Example:

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1 ? : True

Time Complexity: O(n), where n is the length of the smaller dictionary. This is because the algorithm iterates over each key-value pair in the smaller dictionary and performs constant time operations (i.e., checking if a key exists and comparing its value).

Auxiliary Space: O(1), as it only uses constant space for storing variables and does not allocate any extra memory.

Method #5: Using set() intersection method

This program checks whether test_dict2 is a subset of test_dict1 using the set intersection method and prints the result.

It initializes two dictionaries test_dict1 and test_dict2, and prints their original values using print statements.

Then it uses the set intersection method to find the common key-value pairs between the two dictionaries, and checks if the resulting set is equal to the set of key-value pairs in test_dict2. If yes, it returns True, indicating that test_dict2 is a subset of test_dict1, otherwise, it returns False.

Here is the step-by-step approach:

1. Convert both dictionaries to sets of key-value pairs using the items() method.
2. Find the intersection of the sets using the intersection() method.
3. Check if the resulting set is equal to the set of key-value pairs in the smaller dictionary.

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1? : True

Time complexity: O(m+n), where m and n are the sizes of the dictionaries.
Auxiliary space: O(min(m,n)), where m and n are the sizes of the dictionaries.

Method #6: Using dictionary comprehension and all() method

1. The program initializes two dictionaries, test_dict1 and test_dict2, with values {‘gfg’ : 1, ‘is’ : 2, ‘best’ : 3, ‘for’ : 4, ‘CS’ : 5} and {‘gfg’ : 1, ‘is’ : 2, ‘best’ : 3}, respectively.
2. The program creates a new dictionary temp_dict by using a dictionary comprehension that iterates over the key-value pairs of test_dict2 and checks if each key-value pair is present in test_dict1.
3. The program checks if all the key-value pairs in temp_dict evaluate to True, indicating that test_dict2 is a subset of test_dict1.
4. The program prints the resulting boolean value using the print() function.

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1? : True

Time complexity: O(n), where n is the number of key-value pairs in test_dict2.
Auxiliary space: O(n), where n is the number of key-value pairs in test_dict2, to store the key-value pairs in temp_dict

Method #7: Using reduce:

Algorithm:

1. Import the reduce function from the functools module.
2. Initialize two dictionaries test_dict1 and test_dict2.
3. Define a lambda function that takes two inputs a and b and returns a and b.
4. Iterate over the key-value pairs in test_dict2 using the items() method and check if each key is present in
5. test_dict1 and its corresponding value is equal to the value in test_dict2.
6. If the key-value pair is present in test_dict1, the corresponding result is True. Otherwise, the result is False.
7. Store the results in a list using list comprehension.
8. Apply the reduce function to the list of results, using the AND operator to combine the values.Store the final result in the variable res.
9. Print the result.

The original dictionary 1 : {'gfg': 1, 'is': 2, 'best': 3, 'for': 4, 'CS': 5}
The original dictionary 2 : {'gfg': 1, 'is': 2, 'best': 3}
Does dict2 lie in dict1? : True

Time Complexity:
The time complexity of this code is O(n), where n is the number of key-value pairs in test_dict2. This is because we are iterating over each key-value pair in test_dict2 once and performing a constant amount of work for each pair. The reduce function also takes linear time to process the list of results.

Auxiliary Space:
The space complexity of this code is O(n), where n is the number of key-value pairs in test_dict2. This is because we are storing the results of the iteration in a list and then applying the reduce function to the list. The size of the list is proportional to the number of key-value pairs in test_dict2.