Python – Extract elements with equal frequency as value

0 0 5 minutes read

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))

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(1)

Method #2 : Using filter() + lambda + count()

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))

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) 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))

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 #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

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^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

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)
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).