Python – Maximum N repeated Elements
Given List of elements, remove an element if it’s occurrence in list increases more than N.
Input : test_list = [6, 4, 6, 3, 6], N = 1 Output : [6, 4, 3] Explanation : The occurrence 2nd onwards of 6 are removed. Input : test_list = [6, 4, 6, 3, 6], N = 2 Output : [6, 4, 6, 3] Explanation : The occurrence 3rd onwards of 6 are removed.
Method #1 : Using loop + count()
The combination of the above functionalities can be used to solve this problem. In this, we perform an iteration of elements and check if the count is more than N of that element using count(), if yes, then we remove that element.
Python3
# Python3 code to demonstrate working of# Maximum N repeated Elements# Using loop + count()# initializing listtest_list = [5, 7, 7, 2, 5, 5, 7, 2, 2]# printing original listprint("The original list : " + str(test_list))# initializing NN = 2# Using loop + count()res = []for ele in test_list: # checking of elements occurrence is not greater than N if res.count(ele) < N: res.append(ele)# printing resultprint("Extracted elements : " + str(res)) |
The original list : [5, 7, 7, 2, 5, 5, 7, 2, 2] Extracted elements : [5, 7, 7, 2, 5, 2]
Time complexity: O(n^2), where n is the length of the input list test_list. The count() method used in the loop iterates over the list again to count the occurrences of each element, so the total number of iterations becomes n^2 in the worst case.
Auxiliary Space: O(n), where n is the length of the input list test_list. The res list created to store the extracted elements can be the same size as the input list.
Method #2 : Using Counter() + loop
This is yet another way in which this task can be performed. In this, we use Counter() to count elements, and then append its size elements if less than N, if greater, list comprehension is used to extend elements till N. Doesn’t preserve order.
Python3
# Python3 code to demonstrate working of# Maximum N repeated Elements# Using Counter() + loopfrom collections import Counter# initializing listtest_list = [5, 7, 7, 2, 5, 5, 7, 2, 2]# printing original listprint("The original list : " + str(test_list))# initializing NN = 2# Using Counter() + loopres = []temp = Counter(test_list)for key, ele in temp.items(): # Conditional check for size decision during append if ele <= N: res.extend([key for idx in range(ele)]) else: res.extend([key for idx in range(N)])# printing resultprint("Extracted elements : " + str(res)) |
The original list : [5, 7, 7, 2, 5, 5, 7, 2, 2] Extracted elements : [5, 5, 7, 7, 2, 2]
Time complexity: O(n^2), where n is the length of the input list test_list. The count() method used in the loop iterates over the list again to count the occurrences of each element, so the total number of iterations becomes n^2 in the worst case.
Auxiliary Space: O(n), where n is the length of the input list test_list. The res list created to store the extracted elements can be at most the same size as the input list.
Method 3: Using set() and list comprehension
We can also solve this problem by first finding the set of elements that occur at least N times in the list, and then using a list comprehension to extract all occurrences of those elements.
Python3
# initializing listtest_list = [5, 7, 7, 2, 5, 5, 7, 2, 2]# printing original listprint("The original list : " + str(test_list))# initializing NN = 2# Using set() and list comprehensionres = [elem for elem in set(test_list) if test_list.count( elem) >= N for i in range(N)]# printing resultprint("Extracted elements : " + str(res)) |
The original list : [5, 7, 7, 2, 5, 5, 7, 2, 2] Extracted elements : [2, 2, 5, 5, 7, 7]
Time Complexity: O(n^2), where n is the length of the list.
Auxiliary Space: O(k), where k is the number of unique elements in the list.
Method 4: Using defaultdict and loop
- Import the defaultdict from the collections module.
- Initialize an empty dictionary named “freq_dict” using defaultdict. Set the default value to 0.
- Loop through each element in the test_list.
- For each element, increment its count in the freq_dict.
- Initialize an empty list named “res”.
- Loop through each key-value pair in the freq_dict.
- If the value of the key-value pair is greater than or equal to N, then append the key to the res list N times.
- Print the res list as the extracted elements.
Python3
# import defaultdictfrom collections import defaultdict# Initializing listtest_list = [5, 7, 7, 2, 5, 5, 7, 2, 2]# Printing original listprint("The original list : " + str(test_list))# Initializing NN = 2# Using defaultdict and loopfreq_dict = defaultdict(int)for elem in test_list: freq_dict[elem] += 1 res = []for key, value in freq_dict.items(): if value >= N: res += [key] * N# Printing resultprint("Extracted elements : " + str(res)) |
The original list : [5, 7, 7, 2, 5, 5, 7, 2, 2] Extracted elements : [5, 5, 7, 7, 2, 2]
Time complexity: O(n)
Auxiliary space: O(n)
