Python – Common items Dictionary Value List

The functionality of union has been discussed many times. But sometimes, we can have a more complex container, in which we need to check for the intersection of lists which are in form of keys of dictionary. Let’s discuss certain ways to solve this type of problem. 

Method #1: Using Loops Using loops is a naive brute force approach to perform this particular task. In this method, we check for keys present in both list. We even check for the keys completely not present in other to add its whole list value. 

The original dict 1 : {'Key1': [1, 3, 4], 'key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3]}

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

Method #2: Using dictionary comprehension + set operations This is the one line approach to solve the similar problem and offers a compact alternative to above method. This solution processes by using the set comprehension to get the necessary elements bound together into lists using dictionary comprehension. 

The original dict 1 : {'Key1': [1, 3, 4], 'key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3]}

Method #3: Using set and intersection method

This method uses the set() function to get the set of keys that are common to both test_dict1 and test_dict2. Then it loops over these common keys and creates a new dictionary res. For each key, it takes the set intersection of the corresponding value lists using the & operator and converts the resulting set to a list using the list() function. Finally, it assigns the key and the resulting list to the new dictionary res.

The original dict 1 : {'Key1': [1, 3, 4], 'key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3]}

Time complexity: O(N*M), where N and M are the lengths of the value lists in the input dictionaries. 
Auxiliary space: O(N+M), where N and M are the lengths of the value lists in the input dictionaries.

Method #4: Using map and filter

This method uses map and filter functions to iterate over the keys and values of test_dict1. The lambda function in map filters out the values in test_dict1 that are not present in test_dict2, while the lambda function in filter checks if the value is present in test_dict2. The result is a dictionary with the common values for each key in test_dict1 and test_dict2.

The original dict 1 : {'Key1': [1, 3, 4], 'Key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3], 'Key2': []}

Time complexity: O(n*m), where n is the number of keys in test_dict1 and m is the maximum length of the value lists in both dictionaries. 
Auxiliary space: O(n*m), since we are creating a new list of common elements for each key in test_dict1

Method #5: Using set and list comprehension

1. Extract the values of both dictionaries using the ‘values()’ method and convert them to sets using the ‘set()’ function.
2. Use set intersection operation ‘&’ to find the common elements between the two sets.
3. Use list comprehension to create a new list of tuples, where each tuple contains a key from the first dictionary and a list of the common elements between the corresponding values in both dictionaries.
4. Convert the list of tuples into a dictionary using the ‘dict()’ constructor.

The original dict 1 : {'Key1': [1, 3, 4], 'key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3]}

Time Complexity: O(n), where n is the total number of values in both dictionaries.
Auxiliary space: O(n), where n is the total number of values in both dictionaries, as we are storing all the unique values in sets and creating a new dictionary with values containing the common elements between the two input dictionaries.

Method#6: Using Recursive method.

This function takes in two dictionaries dict1 and dict2 as input and returns a new dictionary that contains the common elements of the values in both input dictionaries. The function first checks if either dictionary is empty, and if so, returns an empty dictionary. Otherwise, it pops the first key-value pair from dict1 and finds the intersection of its values with the corresponding key in dict2. Then, it makes a recursive call with the remaining key-value pairs and combines the results. Finally, the function returns the combined dictionary.

The original dict 1 : {'Key1': [1, 3, 4], 'key2': [4, 5]}
The original dict 2 : {'Key1': [1, 7, 3]}
The dicts after intersection is : {'Key1': [1, 3]}

Time complexity:

The function makes recursive calls for each key-value pair in the first dictionary. Therefore, the time complexity is O(N), where N is the number of key-value pairs in the first dictionary.
Finding the intersection of values in both dictionaries takes O(m), where m is the size of the values list.
Overall time complexity can be expressed as O(N * m)
Space complexity:

The function creates a new dictionary to store the common elements, and this dictionary grows as the recursion progresses. Therefore, the space complexity is O(N), where N is the number of key-value pairs in the first dictionary.
 

Method#7: Using numpy:

Algorithm:

1. Initialize the dictionaries test_dict1 and test_dict2.
2. Convert the values of both the dictionaries to numpy arrays.
3. Find the common values using numpy’s intersect1d() function.
4. Create an empty dictionary res.
5. Loop over all the keys in test_dict1.
6. If the key is present in test_dict2, then find the intersection of values for this key in both the dictionaries and with the common values.
7. Store the result in the res dictionary.
8. Print the res dictionary.

Output:
The dicts after intersection is : {'Key1': [1, 3]}

Time Complexity:

Converting the values of both dictionaries to numpy arrays takes O(n) time, where n is the total number of values in both dictionaries.
Finding the common values using numpy’s intersect1d() function takes O(m*log(m)) time, where m is the total number of values in both dictionaries.
Looping over all the keys in test_dict1 takes O(k) time, where k is the total number of keys in test_dict1.
Finding the intersection of values for each key in both dictionaries takes O(n/k*log(n/k)) time.
The overall time complexity of the algorithm is O(n + mlog(m) + k(n/klog(n/k))) = O(nlog(n/k) + m*log(m) + k).

Auxiliary Space:

Converting the values of both dictionaries to numpy arrays requires O(n) space, where n is the total number of values in both dictionaries.
Finding the common values using numpy’s intersect1d() function requires O(m) space, where m is the total number of values in both dictionaries.
Creating an empty dictionary res requires O(1) space.
Storing the intersection of values for each key in the res dictionary requires O(n/k) space for each key.
The overall space complexity of the algorithm is O(n + m + k*n/k) = O(n + m + n) = O(n + m).