Python – Minimum identical consecutive Subarray
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 that has the minimum consecutive occurrence. The knowledge of solution to it can be of great help and can be employed whenever required. Let’s discuss a certain way in which this task can be performed.
Method 1: Using groupby() + min() + lambda This task can be solved using a combination of above functions. In this, we group each occurrence of numbers using groupby() and get the min of it using min(). The lambda function provide utility logic to perform this task.
Python3
# Python3 code to demonstrate working of # Minimum identical consecutive Subarray # using groupby() + min() + lambda from itertools import groupby # initializing list test_list = [ 1 , 1 , 1 , 2 , 2 , 5 , 5 , 5 , 5 ] # printing original list print ("The original list is : " + str (test_list)) # Minimum identical consecutive Subarray # using groupby() + min() + lambda temp = groupby(test_list) res = min (temp, key = lambda sub: len ( list (sub[ 1 ]))) # printing result print ("Minimum Consecutive identical Occurring number is : " + str (res[ 0 ])) |
The original list is : [1, 1, 1, 2, 2, 5, 5, 5, 5] Minimum Consecutive identical Occurring number is : 2
Time Complexity: O(n) where n is the number of elements in the string list. The groupby() + min() + lambda is used to perform the task and it takes O(n) time.
Auxiliary Space: O(1) constant additional space is created.
Method 2: Use numpy library
Note: install numpy module using command “pip install numpy”
The numpy approach uses the unique() function from the numpy library to find the unique elements in the list and their indices and counts. It then finds the minimum count from the count array and uses that to find the corresponding element in the original list.
Python3
import numpy as np test_list = [ 1 , 1 , 1 , 2 , 2 , 5 , 5 , 5 , 5 ] # Using numpy's unique function to find the unique elements, their indices and counts _, index, count = np.unique(test_list, return_index = True , return_counts = True ) # Finding the minimum count min_count = min (count) # Finding the corresponding element in the original list min_element = test_list[index[count = = min_count][ 0 ]] print ( "Minimum Consecutive identical Occurring number is :" , min_element) #This code is contributed by Edula Vinay Kumar Reddy |
Output:
Minimum Consecutive identical Occurring number is : 2
Time complexity: O(n) as it is iterating through the list once.
Space complexity: O(n) as it is storing count of each element in the dictionary.
Method 3 : Using the collections module
Python3
from collections import defaultdict # initializing list test_list = [ 1 , 1 , 1 , 2 , 2 , 5 , 5 , 5 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # create frequency dictionary freq_dict = defaultdict( int ) for elem in test_list: freq_dict[elem] + = 1 # find the minimum value in the dictionary min_value = min (freq_dict.values()) # find the element with minimum frequency for elem, count in freq_dict.items(): if count = = min_value: min_elem = elem break # printing result print ( "Minimum Consecutive identical Occurring number is : " + str (min_elem)) |
The original list is : [1, 1, 1, 2, 2, 5, 5, 5, 5] Minimum Consecutive identical Occurring number is : 2
Time complexity: O(n) – where n is the length of the list, due to the loop to create the frequency dictionary.
Auxiliary space: O(k) – where k is the number of unique elements in the list, due to the frequency dictionary.
Contact Us