Sometimes, while working with Python lists or in competitive programming setup, we can come across a subproblem in which we need to get an element which has the maximum consecutive occurrence. The knowledge of the solution of it can be of great help and can be employed whenever required. Let’s discuss certain ways in which this task can be performed.
Method #1 : Using groupby() + max() + lambda
This task can be solved using combination of above functions. In this, we group each occurrence of numbers using groupby() and get the max of it using max(). The lambda function provide utility logic to perform this task.
Python3
# Python3 code to demonstrate working of# Consecutive Maximum Occurrence in list# using groupby() + max() + lambdafrom itertools import groupby# initializing listtest_list = [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5]# printing original listprint("The original list is : " + str(test_list))# Consecutive Maximum Occurrence in list# using groupby() + max() + lambdatemp = groupby(test_list)res = max(temp, key=lambda sub: len(list(sub[1])))# printing resultprint("Maximum Consecutive Occurring number is : " + str(res[0])) |
Output :
The original list is : [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5] Maximum Consecutive Occurring number is : 5
Time Complexity: O(n)
Auxiliary Space: O(n), where n is length of list.
Method #2: Using a sliding window
- Start with a window of size 1 and move it through the list, updating the maximum element and the maximum number of consecutive occurrences if necessary.
- Initialize two variables to keep track of the current element and the number of consecutive occurrences of that element.
Iterate through the list, comparing the current element to the previous element. - If the current element is the same as the previous element, increment the number of consecutive occurrences. If the current element is different, reset the number of consecutive occurrences to 1.
- Compare the number of consecutive occurrences to the maximum number of consecutive occurrences seen so far, and update the maximum element if necessary.
Python3
def max_consecutive(arr): # Initialize variables to keep track of the current element # and the number of consecutive occurrences of that element max_element = arr[0] max_count = 1 current_element = arr[0] current_count = 1 # Iterate through the list for i in range(1, len(arr)): # Compare the current element to the previous element if arr[i] == arr[i-1]: # If the current element is the same as the previous element, # increment the number of consecutive occurrences current_count += 1 else: # If the current element is different, reset the number of consecutive occurrences to 1 current_count = 1 # Compare the number of consecutive occurrences to the maximum number of consecutive occurrences seen so far if current_count > max_count: # Update the maximum element if necessary max_count = current_count max_element = arr[i] return max_element # initializing listtest_list = [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5] # printing original listprint("The original list is : " + str(test_list))# printing result print("Maximum Consecutive Occurring number is : " + str( max_consecutive(test_list )))#This code is contributed by Edula Vinay Kumar Reddy |
Output
The original list is : [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5] Maximum Consecutive Occurring number is : 5
Time complexity: O(n) where n is the number of elements in the list
Auxiliary Space: O(1)
Method #3: Using a dictionary
- Initialize an empty dictionary called count_dict.
- Initialize a variable called max_count to 0 and a variable called max_num to None.
- Loop through the elements in the test_list.
- If the current element is not in the count_dict, add it with a count of 1. Otherwise, increment its count by 1.
- If the count of the current element is greater than max_count, update max_count to the count and max_num to the current element.
- If the count of the current element is equal to max_count, update max_num to the current element if it comes after the previous max_num in the list.
- After the loop, return max_num as the maximum consecutive occurring number.
Python3
# Python3 code to demonstrate working of# Consecutive Maximum Occurrence in list# using dictionary# initializing listtest_list = [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5]# printing original listprint("The original list is : " + str(test_list))# Consecutive Maximum Occurrence in list# using dictionarycount_dict = {}max_count = 0max_num = Nonefor num in test_list: if num not in count_dict: count_dict[num] = 1 else: count_dict[num] += 1 # If number in dictionary is greater than max_count if count_dict[num] > max_count: # Replace max_count = count_dict[num] max_num = num elif count_dict[num] == max_count and test_list.index(num) > test_list.index(max_num): max_num = num# printing result print("Maximum Consecutive Occurring number is : " + str(max_num)) |
Output
The original list is : [1, 1, 1, 2, 2, 4, 2, 2, 5, 5, 5, 5] Maximum Consecutive Occurring number is : 5
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
