Given a list of integers (elements may be repeated), write a Python program to remove the elements that are repeated less than k times. Examples:
Input : lst = [‘a’, ‘a’, ‘a’, ‘b’, ‘b’, ‘c’], k = 2
Output : [‘a’, ‘a’, ‘a’, ‘b’, ‘b’]Input : lst = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4], k = 3
Output : [1, 1, 1, 1, 3, 3, 3]
Approach #1: Pythonic naive Counter() from the collections module constructs a dictionary mapping values to counts and save them in ‘counted’. Then we make use of ‘temp_lst’ to store the elements that need to be removed. Finally, we traverse through the given list and append all elements that are not in ‘temp_lst’ to ‘res_lst’ containing the required output.
Python3
# Python3 program to Remove elements of # list that repeated less than k timesfrom collections import Counterdef removeElements(lst, k): counted = Counter(lst) temp_lst = [] for el in counted: if counted[el] < k: temp_lst.append(el) res_lst = [] for el in lst: if el not in temp_lst: res_lst.append(el) return(res_lst) # Driver codelst = ['a', 'a', 'a', 'b', 'b', 'c']k = 2print(removeElements(lst, k)) |
['a', 'a', 'a', 'b', 'b']
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach #2: Efficient Approach The efficient approach to use the Counter method is to construct a dictionary mapping value to counts and then use a list comprehension to filter for counts larger than a specified value. This approach is both time and space efficient.
Python3
# Python3 program to Remove elements of # list that repeated less than k timesfrom collections import Counterdef removeElements(lst, k): counted = Counter(lst) return [el for el in lst if counted[el] >= k] # Driver codelst = ['a', 'a', 'a', 'b', 'b', 'c']k = 2print(removeElements(lst, k)) |
['a', 'a', 'a', 'b', 'b']
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach #3 : Using list(),set(),count() methods
Python3
# Python3 program to Remove elements of# list that repeated less than k timeslst = ['a', 'a', 'a', 'b', 'b', 'c']k = 2x=list(set(lst))for i in x: if lst.count(i)<k: lst.remove(i) print(lst) |
['a', 'a', 'a', 'b', 'b']
Time Complexity: O(N)
Auxiliary Space: O(N)
Method#4: Using Recursive method.
Algorithm:
- Define a function remove_repeated(lst, k, i=0) that takes a list lst, an integer k, and an optional index i.
- If i is equal to the length of lst, return lst.
- If the count of the element at index i in lst is less than k, remove the element using the remove() method.
- If the count of the element at index i in lst is not less than k, increment i by 1 and call remove_repeated(lst, k, i).
- Return the modified list.
Python3
def remove_repeated(lst, k, i = 0): if i == len(lst):return lst elif lst.count(lst[i]) < k: lst.remove(lst[i]) return remove_repeated(lst, k) else:return remove_repeated(lst, k, i + 1)lst = ['a', 'a', 'a', 'b', 'b', 'c']k = 2result = remove_repeated(lst, k)print(result)#this code contributed by tvsk |
['a', 'a', 'a', 'b', 'b']
The time complexity of this algorithm is O(n^2), where n is the length of the list lst. This is because the count() method takes O(n) time to search the list for the element, and the remove() method takes O(n) time to remove the element and adjust the indices of all subsequent elements. Since these operations are performed in a loop that iterates n times, the overall time complexity is O(n^2).
The auxiliary space complexity of this algorithm is O(1), because it only uses a constant amount of additional space to store the index i and any temporary variables used in the loop. The list lst is modified in place, so no additional copies are made.
