Python – Extract elements with equal frequency as value
Given a list, extract all the elements having same frequency as its value.
Examples:
Input : test_list = [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4]
Output : [1, 3, 4]
Explanation : All elements occur equal times as their value.
Input : test_list = [4, 3, 2, 2, 3, 4, 1, 3, 2, 4]
Output : [1, 3]
Explanation : All elements occur equal times as their value.
Method #1 : Using list comprehension + count()
In this, task of getting frequency is done using count(), list comprehension is used to iterate for each element, compare and extract.
Python3
# Python3 code to demonstrate working of # Extract elements with equal frequency as value # Using list comprehension + count() # initializing list test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] # printing original list print ( "The original list is : " + str (test_list)) # removing duplicates using set() # count() for computing frequency res = list ( set ([ele for ele in test_list if test_list.count(ele) = = ele])) # printing result print ( "Filtered elements : " + str (res)) |
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time Complexity: O(n)
Auxiliary Space: O(1)
In this, we perform task of filtering elements using filter() and lambda, count() again is used to get count of all the elements.
Python3
# Python3 code to demonstrate working of # Extract elements with equal frequency as value # Using filter() + lambda + count() # initializing list test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] # printing original list print ( "The original list is : " + str (test_list)) # removing duplicates using set() # count() for computing frequency # filter used to perform filtering res = list ( set ( list ( filter ( lambda ele : test_list.count(ele) = = ele, test_list)))) # printing result print ( "Filtered elements : " + str (res)) |
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time Complexity: O(n) where n is the number of elements in the list “test_list”. This is because we’re using the built-in filter() + lambda + count() which all has a time complexity of O(n) in the worst case.
Auxiliary Space: O(1), no extra space is required
Method #3 : Using Counter() + items() + sort()
Python3
# Python3 code to demonstrate working of # Extract elements with equal frequency as value from collections import Counter # initializing list test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] # printing original list print ( "The original list is : " + str (test_list)) freq = Counter(test_list) res = [] for key, value in freq.items(): if (key = = value): res.append(key) res.sort() # printing result print ( "Filtered elements : " + str (res)) |
Output
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4 : Using list comprehension + operator.countOf()
In this, task of getting frequency is done using operator.countOf(), list comprehension is used to iterate for each element, compare and extract.
Python3
# Python3 code to demonstrate working of # Extract elements with equal frequency as value # Using list comprehension + operator.countOf() import operator as op # initializing list test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] # printing original list print ( "The original list is : " + str (test_list)) # removing duplicates using set() # operator.countOf() for computing frequency res = list ( set ([ele for ele in test_list if op.countOf(test_list,ele) = = ele])) # printing result print ( "Filtered elements : " + str (res)) |
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using numpy module
Algorithm:
- Initialize the input list.
- Print the original list.
- Create a new list by iterating over the input list using a list comprehension.
- For each element in the input list, check if its frequency is equal to its value using the count() method.
- If the frequency is equal to the value, add the element to the new list.
- Remove duplicates from the new list using the set() method.
- Convert the set back to a list and store it in the variable “res”.
- Print the filtered elements.
Python3
# initializing list test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] # printing original list print ( "The original list is : " + str (test_list)) # removing duplicates using set() # count() for computing frequency # list comprehension to filter out elements with equal frequency as value res = list ( set ([ele for ele in test_list if test_list.count(ele) = = ele])) # printing result print ( "Filtered elements : " + str (res)) # This code is contributed by Jyothi pinjala |
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time complexity: O(n^2) (due to the use of count() method within the list comprehension)
Auxiliary Space: O(n) (due to the creation of a new list to store the filtered elements)
Method #6: Using recursion
Algorithm:
- Define a recursive function count_freq that takes a list test_list, an element ele and an integer count as input.
- The function returns the frequency of the element ele in the list test_list.
- If the input test_list is empty, the function returns the value of count.
- If the first element of test_list is equal to ele, increment count by 1.
- Recursively call the count_freq function with the remainder of test_list and the same ele and count.
- Define a function filter_elements that takes a list test_list as input.
- Initialize an empty list res.
- Iterate over the set of unique elements in test_list.
- If the frequency of the current element in test_list is equal to the value of the element, append the element to res.
- Return res.
Python3
def count_freq(test_list, ele, count = 0 ): if not test_list: return count if test_list[ 0 ] = = ele: count + = 1 return count_freq(test_list[ 1 :], ele, count) def filter_elements(test_list): res = [] for ele in set (test_list): if count_freq(test_list, ele) = = ele: res.append(ele) return res test_list = [ 4 , 3 , 2 , 2 , 3 , 4 , 1 , 3 , 2 , 4 , 4 ] print ( "The original list is : " + str (test_list)) filtered_list = filter_elements(test_list) print ( "Filtered elements : " + str (filtered_list)) #This code is contributed by Rayudu |
The original list is : [4, 3, 2, 2, 3, 4, 1, 3, 2, 4, 4] Filtered elements : [1, 3, 4]
Time complexity: O(n)
Where n is the length of the input test_list. The filter_elements function iterates over the set of unique elements in test_list, and for each element, calls the count_freq function, which has a time complexity of O(n). Therefore, the time complexity of the entire algorithm is O(n^2).
Auxiliary Space: O(n)
Due to the recursive calls on the stack. The filter_elements function stores a list of unique elements in test_list, which has a space complexity of O(n) and creates a list res to store the filtered elements, which has a space complexity of O(m) where m is the number of filtered elements. Therefore, the overall space complexity of the algorithm is O(n + m).