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 listtest_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]# printing original listprint("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 listtest_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]# printing original listprint("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 Kfrom collections import Counter# initializing listtest_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 1for i in test_list.copy(): freq = Counter(i) for key, value in freq.items(): if(value <= K): test_list.remove(i) break# printing resultprint("Filtered rows : " + str(test_list)) |
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 listtest_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]# printing original listprint("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)) |
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 listtest_list = [[1, 1, 2, 3, 2, 3], [4, 4, 5, 6, 6], [1, 1, 1, 1], [4, 5, 6, 8]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 1# filtering list based on conditionres = [ele for ele in test_list if all(np.count_nonzero(np.array(ele) == x) > K for x in ele)]# printing resultprint("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 rowsfiltered_list = []# iterate over each row in the input listfor 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 listprint("Filtered rows:", filtered_list) |
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).
