Python program to print Rows where all its Elements’ frequency is greater than K

0 0 6 minutes read

Given Matrix, extract all rows whose all elements have a frequency greater than K.

Input : test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]], K = 2
Output : [[1, 1, 1, 1]]
Explanation : Here, frequency of 1 is 4 > 2, hence row retained.

Input : test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 3, 4, 1], [4, 5, 6, 8]], K = 2
Output : []
Explanation : No list filtered as result.

Method #1 : Using list comprehension + all() + count()

In this, we perform task of iterating through elements using list comprehension and all() is used to check for each elements count(), extracted using count().

Python3

# Python3 code to demonstrate working of 
# Rows with all Elements frequency greater than K
# Using list comprehension + count() + all()
 
def freq_greater_K(row, K) :
     
    # checking for all elements occurrence greater than K 
    return all(row.count(ele) > K for ele in row)
 
# initializing list
test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K 
K = 1
 
# checking for each row 
res = [ele for ele in test_list if freq_greater_K(ele, K)]
 
# printing result 
print("Filtered rows : " + str(res))

Output:

The original list is : [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]] Filtered rows : [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time Complexity: O(n)
Auxiliary Space: O(n)

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

In this, task of filtering is done using filter() + lambda, all() is used to check for each element, count() to compute count.

Python3

# Python3 code to demonstrate working of 
# Rows with all Elements frequency greater than K
# Using filter() + lambda + all() + count()
 
def freq_greater_K(row, K) :
     
    # checking for all elements occurrence greater than K 
    return all(row.count(ele) > K for ele in row)
 
# initializing list
test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K 
K = 1
 
# checking for each row 
res = list(filter(lambda ele : freq_greater_K(ele, K), test_list))
 
# printing result 
print("Filtered rows : " + str(res))

Output:

The original list is : [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]] Filtered rows : [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time Complexity: O(n*n) where n is the number of elements in the list “test_list”. filter() + lambda + all() + count() performs n*n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list

Method #3: Using Counter() function

Python3

# Python3 code to demonstrate working of
# Rows with all Elements frequency greater than K
from collections import Counter
 
# initializing list
test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K
K = 1
 
for i in test_list.copy():
    freq = Counter(i)
    for key, value in freq.items():
        if(value <= K):
            test_list.remove(i)
            break
 
 
# printing result
print("Filtered rows : " + str(test_list))

Output

The original list is : [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
Filtered rows : [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time Complexity: O(N*N)
Auxiliary Space : O(N)

Method 4: Using operator.countOf() function

Python3

import operator as op
# Python3 code to demonstrate working of 
# Rows with all Elements frequency greater than K
# Using list comprehension + operator.countOf() + all()
 
def freq_greater_K(row, K) :
     
    # checking for all elements occurrence greater than K 
    return all(op.countOf(row,ele) > K for ele in row)
 
# initializing list
test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing K 
K = 1
 
# checking for each row 
res = [ele for ele in test_list if freq_greater_K(ele, K)]
 
# printing result 
print("Filtered rows : " + str(res))

Output

The original list is : [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
Filtered rows : [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time Complexity: O(N*N)
Auxiliary Space : O(N)

Method 5: Using numpy:

Algorithm:

Initialize a list of lists named “test_list” and a variable K with the given values.
Filter the list “test_list” using list comprehension and check whether all the elements of each sublist occur more than K times or not.
To check the frequency of each element of the sublist, we first convert the sublist into a numpy array using np.array() function.

Python3

import numpy as np
# initializing list
test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
# printing original list
print("The original list is : " + str(test_list))
# initializing K
K = 1
# filtering list based on condition
res = [ele for ele in test_list if all(np.count_nonzero(np.array(ele) == x) > K for x in ele)]
# printing result
print("Filtered rows : " + str(res))
#This code is contributed by Jyothi pinjala.

Output:

The original list is : [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
Filtered rows : [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time complexity:
The time complexity of the above code is O(n * m * k) where n is the number of rows, m is the maximum length of any row, and k is the value of K. Here, we are iterating over all the rows and then for each row, we are iterating over each element and then counting its frequency using np.count_nonzero() function. Therefore, the time complexity of this code is directly proportional to the size of the input.

Space complexity:
The space complexity of the above code is O(n * m) where n is the number of rows and m is the maximum length of any row. Here, we are creating a new list of filtered rows and storing the elements that pass the condition. Therefore, the space complexity of this code is directly proportional to the size of the input

Method #6 : Using a nested loop and a flag variable

Step-by-step approach:

Initialize a list of lists, test_list, containing 4 sub-lists of integers.
Set the value of K to 1.
Initialize an empty list filtered_list to store the rows that have all elements with frequency greater than K.
Iterate over each sub-list in test_list using a for loop.
For each sub-list, set a flag variable flag to True.
Iterate over each element in the sub-list using another for loop.
Count the frequency of the current element in the sub-list using the count() method.
If the frequency of the current element is less than or equal to K, set the flag to False and break out of the loop.
If the flag is still True after checking all elements, add the sub-list to filtered_list.
After iterating over all sub-lists, print the filtered_list to show the rows that have all elements with frequency greater than K.

Python3

test_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]
K = 1
 
# initialize an empty list to store the filtered rows
filtered_list = []
 
# iterate over each row in the input list
for row in test_list:
    # set a flag variable to True
    flag = True
    # iterate over each element in the row
    for element in row:
        # count the frequency of the element in the row
        frequency = row.count(element)
        # if the frequency is less than or equal to K, set the flag to False and break out of the loop
        if frequency <= K:
            flag = False
            break
    # if the flag is still True after checking all elements, add the row to the filtered list
    if flag:
        filtered_list.append(row)
 
# print the filtered list
print("Filtered rows:", filtered_list)

Output

Filtered rows: [[1, 1, 2, 3, 2, 3], [1, 1, 1, 1]]

Time complexity: O(n^2), where n is the total number of elements in the input list.
Auxiliary space: O(m), where m is the number of rows in the input list (used to store the filtered rows).