Given a dictionary, the task is to find keys with duplicate values. Let’s discuss a few methods for the same.
Method #1: Using Naive approach In this method first, we convert dictionary values to keys with the inverse mapping and then find the duplicate keys
Python3
# Python code to demonstrate# finding duplicate values from a dictionary# initialising dictionaryini_dict = {'a':1, 'b':2, 'c':3, 'd':2}# printing initial_dictionaryprint("initial_dictionary", str(ini_dict))# finding duplicate values# from dictionary# using a naive approachrev_dict = {}for key, value in ini_dict.items(): rev_dict.setdefault(value, set()).add(key) result = [key for key, values in rev_dict.items() if len(values) > 1]# printing resultprint("duplicate values", str(result)) |
initial_dictionary {'c': 3, 'b': 2, 'd': 2, 'a': 1}
duplicate values [2]
Time Complexity: O(n), where n is the number of elements in the dictionary.
Auxiliary Space: O(n)
Method #2: Using flipping dictionary
Python3
# Python code to demonstrate# finding duplicate values from dictionary# initialising dictionaryini_dict = {'a':1, 'b':2, 'c':3, 'd':2}# printing initial_dictionaryprint("initial_dictionary", str(ini_dict))# finding duplicate values# from dictionary using flipflipped = {}for key, value in ini_dict.items(): if value not in flipped: flipped[value] = [key] else: flipped[value].append(key)# printing resultprint("final_dictionary", str(flipped)) |
initial_dictionary {'a': 1, 'c': 3, 'd': 2, 'b': 2}
final_dictionary {1: ['a'], 2: ['d', 'b'], 3: ['c']}
Time complexity: O(n), where n is the number of key-value pairs in the input dictionary.
Auxiliary space: O(n), where n is the number of key-value pairs in the input dictionary.
Method #3: Using chain and set Suppose you need to find keys having duplicate values.
Python3
# Python code to demonstrate# finding duplicate values from dictionaryfrom itertools import chain# initialising dictionaryini_dict = {'a':1, 'b':2, 'c':3, 'd':2}# printing initial_dictionaryprint("initial_dictionary", str(ini_dict))# finding duplicate values# from dictionary using setrev_dict = {}for key, value in ini_dict.items(): rev_dict.setdefault(value, set()).add(key)result = set(chain.from_iterable( values for key, values in rev_dict.items() if len(values) > 1))# printing resultprint("resultant key", str(result)) |
initial_dictionary {'b': 2, 'd': 2, 'c': 3, 'a': 1}
resultant key {'d', 'b'}
Instead of
Python3
result = set(chain.from_iterable( values for key, values in rev_dict.items() if len(values) > 1)) |
Use this:
Python3
result = filter(lambda x: len(x)>1, rev_dict.values())print(list(result)) |
Using collections:
One approach not mentioned is to use a Counter from the collections module. A Counter is a dictionary subclass that keeps track of the number of occurrences of each element. You can use a Counter to find the keys with duplicate values by counting the values and creating a new dictionary with only the keys whose value has a count greater than 1.
Here’s an example of how to do this:
Python3
from collections import Counter# Initialize the dictionaryini_dict = {'a':1, 'b':2, 'c':3, 'd':2}# Create a Counter from the dictionary valuescounts = Counter(ini_dict.values())# Create a new dictionary with only the keys whose value has a count greater than 1result = {k: v for k, v in ini_dict.items() if counts[v] > 1}print(result.keys())#This code is contributed by Edula Vinay Kumar Reddy |
dict_keys(['b', 'd'])
Time complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using Counter
This method involves using the Counter module from the collections library to count the occurrences of values in the dictionary. Then extract the keys with count greater than 1 to get the duplicate values.
Step-by-Step Approach:
- Import the Counter module from the collections library.
- Initialize the dictionary with values.
- Create a Counter object using the dictionary values.
- Iterate through the Counter object and extract the keys with count greater than 1 to get the duplicate values.
- Print the duplicate values.
Below is the implementation of the above approach:
Python3
# Python code to demonstrate# finding duplicate values from a dictionary# import Counter module from collections libraryfrom collections import Counter# initialising dictionaryini_dict = {'a':1, 'b':2, 'c':3, 'd':2}# printing initial_dictionaryprint("initial_dictionary", str(ini_dict))# finding duplicate values# from dictionary# using Countercount_dict = Counter(ini_dict.values())result = [key for key, value in ini_dict.items() if count_dict[value] > 1]# printing resultprint("duplicate values", str(result)) |
initial_dictionary {'a': 1, 'b': 2, 'c': 3, 'd': 2}
duplicate values ['b', 'd']
Time Complexity: O(n), where n is the number of elements in the dictionary.
Auxiliary Space: O(n), where n is the number of elements in the dictionary.
