Python – Common keys in list and dictionary

Given a dictionary and list, extract all the keys and list which are common.

Input : test_dict = {“Gfg”: 3, “is” : 5, “best” : 9, “for” : 0, “Lazyroar” : 3}, test_list = [“Gfg”, “best”, “CS”] Output : [‘Gfg’, ‘best’] Explanation : Gfg and best are present in both dictionary and List. Input : test_dict = {“Gfg”: 3, “is” : 5, “best” : 9, “for” : 0, “Lazyroar” : 3}, test_list = [“Gfg”, “good”, “CS”] Output : [‘Gfg’] Explanation : Gfg is present in both dictionary and List.

Method #1 : Using list comprehension

This is one of the ways in which this task can be performed. In this, we iterate for all the dictionary and list values, if find a match, they are added to result.

The original dictionary is : {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result : ['Gfg', 'best', 'Lazyroar']

Method #2 : Using set() + intersection()

This is yet another way in which this task can be performed. In this, we convert both the containers, list and dictionary keys to set() and then intersect to find required match.

The original dictionary is : {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result : ['best', 'Lazyroar', 'Gfg']

The time complexity of this program is O(m+n), where m is the length of test_list and n is the number of keys in test_dict.

The auxiliary space complexity is O(k), where k is the number of common elements between test_list and the keys of test_dict.

Method #3: Using keys() method and in operator

The original dictionary is : {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result : ['Gfg', 'best', 'Lazyroar']

The time complexity of this code is O(n), where n is the number of keys in the ‘test_dict’ dictionary. 

The space complexity of this code is O(n+m), where n is the number of keys in the ‘test_dict’ dictionary and m is the number of elements in ‘test_list’. 

Method #4: Using Counter() function

The original dictionary is : {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result : ['Gfg', 'best', 'Lazyroar']

Time Complexity: O(N) as searching in list takes O(1)

Auxiliary Space: O(N)

Method #5: Using reduce()

1. Set the variable res to True
2. For each key key in test_list, do the following:
    a. Check if key is present in test_dict
    b. If key is not present in test_dict, set res to False and break out of the loop
3. If res is True, get the common keys between test_list and test_dict
4. Return the common keys as the result.

The original dictionary is : {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result : ['Gfg', 'best', 'Lazyroar']

Time complexity:

The loop that iterates over each key in the list has a time complexity of O(n), where n is the length of the list.
The time complexity of checking if a key is present in a dictionary using the in operator is O(1) on average, so the time complexity of the loop that checks for common keys is also O(n).
Finally, the list comprehension that gets the common keys has a time complexity of O(k), where k is the number of common keys between the list and the dictionary.
Therefore, the total time complexity of the algorithm is O(n + k).
Auxiliary Space:

The space complexity of the algorithm is O(n + m + k), where n is the length of the list, m is the number of keys in the dictionary, and k is the number of common keys between the list and the dictionary.
We need to store the list, dictionary, and the list of common keys in memory, so the space complexity is proportional to their size.
Therefore, the space complexity of the algorithm is O(n + m + k).

Method #6: Using numpy():

1. Import the numpy library and define a dictionary test_dict and a list test_list.
2. Next, we convert the test_list into a numpy array using the numpy.array() method and store it in the arr_list variable.
3. We then create a new list common_keys using a list comprehension that iterates over the keys in test_dict. For each key, we check if it is present in the numpy array arr_list. If it is, we add it to the common_keys list.
4. Finally, we print the original Dictionary and the common_keys list.

Output:

The original dictionary is: {'Gfg': 3, 'is': 5, 'best': 9, 'for': 0, 'Lazyroar': 3}
The required result: ['Gfg', 'best', 'Lazyroar']

Time Complexity:

The conversion of the list to a numpy array has a time complexity of O(n), where n is the length of the list.
The iteration over the dictionary keys has a time complexity of O(k), where k is the number of keys in the dictionary.
The in operator for checking whether a key is present in the numpy array has an average time complexity of O(log n), where n is the length of the array.
Therefore, the overall time complexity of the algorithm is O(k log n), where k is the number of keys in the dictionary and n is the length of the numpy array.

Space Complexity:

The numpy array created from the list takes up O(n) space.
The common_keys list takes up space proportional to the number of common keys, which is at most min(k, n).
Therefore, the overall space complexity of the algorithm is O(n + min(k, n)).