Sometimes, while working with data, we can have a problem in which we need to extract element which is occurring least number of times in the list. Let’s discuss certain ways in which this problem can be solved.
Method #1: Using defaultdict() + loop The combination of above functions can be used to perform this task. In this, we extract each element’s frequency using defaultdict() and extract the minimum frequency element after traversing the defaultdict.
Python3
# Python3 code to demonstrate working of# Extract least frequency element# using defaultdict() + loopfrom collections import defaultdict# initialize listtest_list = [1, 3, 4, 5, 1, 3, 5]# printing original listprint("The original list : " + str(test_list))# Extract least frequency element# using defaultdict() + loopres = defaultdict(int)for ele in test_list: res[ele] += 1 min_occ = 9999for ele in res: if min_occ > res[ele]: min_occ = res[ele] tar_ele = ele# printing resultprint("The minimum occurring element is : " + str(tar_ele)) |
The original list : [1, 3, 4, 5, 1, 3, 5] The minimum occurring element is : 4
Time Complexity: O(n*n), where n is the length of the input list. This is because we’re using defaultdict() + loop which has a time complexity of O(n*n) in the worst case.
Auxiliary Space: O(1), as we’re using constant additional space
Method #2: Using Counter() This method is similar to above, the difference is that the frequency is stored using Counter() and then we extract element with least frequency.
Python3
# Python3 code to demonstrate working of# Extract least frequency element# using Counter()from collections import Counter# initialize list test_list = [1, 3, 4, 5, 1, 3, 5]# printing original list print("The original list : " + str(test_list))# Extract least frequency element# using Counterres = Counter(test_list)tar_ele = res.most_common()[-1][0]# printing resultprint("The minimum occurring element is : " + str(tar_ele)) |
The original list : [1, 3, 4, 5, 1, 3, 5] The minimum occurring element is : 4
Time complexity: O(n), where n is the length of the numbers list. The counter() function has a time complexity of O(n)
Auxiliary Space: O(n),where n is the length of the numbers list. This is because the counter() function creates an intermediate result for each element of the numbers list, which requires additional memory.
Method #3 : Using set() and list comprehension
In this method, we can use set() to get the unique elements from the given list and then use list comprehension to find the least occurring element.
Python3
# Python3 code to demonstrate working of# Extract least frequency element# using set() and list comprehension# initialize list test_list = [1, 3, 4, 5, 1, 3, 5]# printing original list print("The original list : " + str(test_list))# Extract least frequency element# using set() and list comprehensionunique_elements = set(test_list)min_occ = min([test_list.count(x) for x in unique_elements])tar_ele = [x for x in unique_elements if test_list.count(x) == min_occ]# printing resultprint("The minimum occurring element is : " + str(tar_ele))#this code is contributed by edula vinay kumar reddy |
The original list : [1, 3, 4, 5, 1, 3, 5] The minimum occurring element is : [4]
Time Complexity: O(n) where n is the length of the list.
Auxiliary Space: O(n) where n is the length of the list.
Method #4: Using a dictionary to store the frequency of each element:
Python3
test_list = [1, 3, 4, 5, 1, 3, 5]freq_dict = {}for i in test_list: if i not in freq_dict: freq_dict[i] = 1 else: freq_dict[i] += 1min_occ = min(freq_dict.values())tar_ele = [k for k, v in freq_dict.items() if v == min_occ]# printing original listprint("The original list : " + str(test_list)) print("The minimum occurring element is:", tar_ele)#This code is contributed by Jyothi pinjala. |
The original list : [1, 3, 4, 5, 1, 3, 5] The minimum occurring element is: [4]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using heapq library
Use the heapq library to extract the least frequency element. The idea is to iterate over each element in the list and store its frequency in a dictionary. Then, use the heapq library to find the smallest value in the dictionary, which will be the least frequency element.
Python3
import heapq# initialize listtest_list = [1, 3, 4, 5, 1, 3, 5]# printing original listprint("The original list : " + str(test_list))# create a dictionary to store the frequency of each elementfreq_dict = {}for elem in test_list: if elem in freq_dict: freq_dict[elem] += 1 else: freq_dict[elem] = 1# use heapq library to find the smallest value in the dictionarymin_occ = heapq.nsmallest(1, freq_dict.values())[0]# find all elements that occur with the minimum frequencytar_ele = [k for k, v in freq_dict.items() if v == min_occ]# printing resultprint("The minimum occurring element is : " + str(tar_ele)) |
The original list : [1, 3, 4, 5, 1, 3, 5] The minimum occurring element is : [4]
Time complexity: O(nlogk), where n is the length of the list and k is the number of distinct elements in the list.
Auxiliary space: O(k), since we need to store the frequency of each element in the dictionary.
