Given a List, extract all elements whose frequency is greater than K.
Input : test_list = [4, 6, 4, 3, 3, 4, 3, 4, 3, 8], K = 3
Output : [4, 3]
Explanation : Both elements occur 4 times.Input : test_list = [4, 6, 4, 3, 3, 4, 3, 4, 6, 6], K = 2
Output : [4, 3, 6]
Explanation : Occur 4, 3, and 3 times respectively.
Method #1 : Using count() + loop
In this, we use count() to get the frequency, and a loop is used to iterate for each of the elements of the List.
Python3
# Python3 code to demonstrate working of # Extract elements with Frequency greater than K# Using count() + loop# initializing listtest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8]# printing stringprint("The original list : " + str(test_list))# initializing K K = 2res = [] for i in test_list: # using count() to get count of elements freq = test_list.count(i) # checking if not already entered in results if freq > K and i not in res: res.append(i)# printing results print("The required elements : " + str(res)) |
The original list : [4, 6, 4, 3, 3, 4, 3, 7, 8, 8] The required elements : [4, 3]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using list comprehension + Counter()
In this, we perform the task of counting using Counter() and the iteration part is done inside list comprehension.
Python3
# Python3 code to demonstrate working of # Extract elements with Frequency greater than K# Using list comprehension + Counter()from collections import Counter# initializing listtest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8]# printing stringprint("The original list : " + str(test_list))# initializing K K = 2# using list comprehension to bind resultres = [ele for ele, cnt in Counter(test_list).items() if cnt > K]# printing results print("The required elements : " + str(res)) |
The original list : [4, 6, 4, 3, 3, 4, 3, 7, 8, 8] The required elements : [4, 3]
Time complexity: O(n), where n is the length of the test_list. The list comprehension + Counter() takes O(n) time
Auxiliary Space: O(n), extra space of size n is required
Method #3: Using a dictionary
In this we keep count of the elements, if the count of the element id K + 1, we add that element to the output.
Python3
test_list = [4, 6, 4, 3, 3, 4, 3, 4, 6, 6]k = 2unique_elems = []freq_dict = {}output = []# printing stringprint("The original list : " + str(test_list))for i in test_list: # Append in the unique element list if i not in unique_elems: unique_elems.append(i) freq_dict[i] = 1 else: # increment the counter if element is duplicate freq_dict[i] += 1 # Add in the output list only once if freq_dict[i] == k + 1: output.append(i)print('The required elements : ', str(output)) |
The original list : [4, 6, 4, 3, 3, 4, 3, 4, 6, 6] The required elements : [4, 3, 6]
Time Complexity: O(n), where n is the length test_list.
Auxiliary Space: O(n), where n is number of elements in output list.
Method #4: Using operator.countOf() method
Python3
# Python3 code to demonstrate working of# Extract elements with Frequency greater than Kimport operator as op# initializing listtest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8]# printing stringprint("The original list : " + str(test_list))# initializing KK = 2unique_elements = set(test_list)res = []for i in unique_elements: # using operatorcountOf() to get count of elements if op.countOf(test_list, i) > K: res.append(i)# printing resultsprint("The required elements : " + str(res)) |
The original list : [4, 6, 4, 3, 3, 4, 3, 7, 8, 8] The required elements : [3, 4]
Time Complexity:O(N)
Auxiliary Space:O(N)
Method#5: using NumPy module
Python3
import numpy as nptest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8]K = 2# use numpy unique to extract unique elements and their frequencyunique_elements, counts = np.unique(test_list, return_counts=True)# extract elements with frequency greater than Kres = unique_elements[counts > K].tolist()# printing resultsprint("The required elements : " + str(res))#this code is contributed by Asif_Shaik |
Output:
The required elements : [3, 4]
Time Complexity:O(N)
Auxiliary Space:O(N)
Method #6: Using filter() and lambda()
Algorithm:
- Import the Counter class from the collections module.
- Define the input list test_list and the threshold value K.
- Use the Counter class to count the frequency of each element in the test_list.
- Use the filter() function with a lambda function to keep only the elements whose frequency is greater than K.
- Convert the result into a list and print it
Python3
from collections import Countertest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8]K = 2freq_dict = Counter(test_list)res = list(filter(lambda ele: freq_dict[ele] > K, freq_dict))print("The required elements : " + str(res))#This code is contributed By Vinay Pinjala. |
The required elements : [4, 3]
Time Complexity:
The time complexity of this code is O(n), where n is the length of the input list. This is because the Counter() function from the collections module has a time complexity of O(n), where n is the number of elements in the list. The filter() function and the conversion to a list take linear time, which is also O(n).
Auxiliary Space:
The space complexity of this code is also O(n), where n is the length of the input list. This is because the Counter() function creates a dictionary that stores the frequency count of each element, and the size of this dictionary is proportional to the number of elements in the input list. The output list created by filter() can also be at most n elements long, so the space complexity of the final result is also O(n).
Method #7: Using defaultdict module from the collections library:
Algorithm:
- Import the defaultdict module from the collections library.
- Initialize an empty dictionary, freq_dict, using defaultdict(int) to store the frequency count of each element in the test_list.
- Set the value of K.
- Loop through each key-value pair in freq_dict.
- If the frequency of an element is greater than K, append that element to the res list.
- Print the final result.
Python3
from collections import defaultdict# initializing listtest_list = [4, 6, 4, 3, 3, 4, 3, 7, 8, 8] # printing stringprint("The original list : " + str(test_list)) freq_dict = defaultdict(int)for num in test_list: freq_dict[num] += 1K = 2res = []for num, freq in freq_dict.items(): if freq > K: res.append(num)# printing resultsprint("The required elements : " + str(res))#This code is contributed by Jyothi Pinjala. |
The original list : [4, 6, 4, 3, 3, 4, 3, 7, 8, 8] The required elements : [4, 3]
Time Complexity: O(n), where n is the length of the input list. This is because we iterate through the list once to build the frequency dictionary and once again to find elements with frequency greater than K.
Auxiliary Space: O(n), where n is the length of the input list. This is because we store the frequency counts of each element in the test_list in the freq_dict dictionary. The space taken by the res list is proportional to the number of elements with frequency greater than K. However, the worst-case scenario is when all elements have a unique frequency count, resulting in a dictionary with n key-value pairs.
