Some of the classical problems in programming domain comes from different categories and one among them is finding the minimum of subsets. This particular problem is also common when we need to accumulate the minimum and store consecutive group minimum. Let’s try different approaches to this problem in python language.
Method #1 : Using list comprehension + min() The list comprehension can be used to perform the this particular task to filter out successive groups and min function can be used to get the minimum of the filtered solution.
Python3
# Python3 code to demonstrate # Consecutive Subsets Minimum # using list comprehension + min() # initializing list test_list = [4, 7, 8, 10, 12, 15, 13, 17, 14] # printing original list print("The original list : " + str(test_list)) # using list comprehension + min() # Consecutive Subsets Minimum res = [ min(test_list[x : x + 3]) for x in range(0, len(test_list), 3)] # printing result print("The grouped minimum list is : " + str(res)) |
The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14] The grouped minimum list is : [4, 10, 13]
Time Complexity: O(n) where n is the number of elements in the in the list “test_list”. The list comprehension + min() is used to perform the task and it takes O(n) time.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the in the list “test_list”.
Method #2 : Using min() + itertools.islice() The task of slicing the list into chunks is done by islice method here and the conventional task of getting the minimum is done by the min function as the above method.
Python3
# Python3 code to demonstrate # Consecutive Subsets Minimum # using itertools.islice() + min() import itertools # initializing list test_list = [4, 7, 8, 10, 12, 15, 13, 17, 14] # printing original list print("The original list : " + str(test_list)) # using itertools.islice() + min() # Consecutive Subsets Minimum res = [min(list(itertools.islice(test_list, i, i + 3))) for i in range(0, len(test_list), 3)] # printing result print("The grouped minimum list is : " + str(res)) |
The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14] The grouped minimum list is : [4, 10, 13]
Time Complexity: O(n*n), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.
Method #3 : Using numpy.array_split() + min()
Note: Install numpy module using command “pip install numpy”
In this approach, we can use the numpy library’s array_split() function to split the original list into consecutive chunks of a specified size and then use the min() function to find the minimum value in each chunk.
Python3
import numpy as np# initializing listtest_list = [4, 7, 8, 10, 12, 15, 13, 17, 14]# printing original list print("The original list : " + str(test_list))# Using numpy.array_split() + min()# Consecutive Subsets Minimumres = [min(chunk) for chunk in np.array_split(test_list, len(test_list)//3)]# printing resultprint("The grouped minimum list is : " + str(res))#This code is contributed by Edula Vinay Kumar Reddy |
Output:
The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14]
The grouped minimum list is : [4, 10, 13]
Time Complexity: O(n) where n is the number of elements in the string list. The numpy is used to perform the task and it takes O(n) time.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the test list.
Method #4 :Using heapq:
Algorithm:
- Initialize an empty list res.
- Loop through the original list in increments of 3.
- For each 3 consecutive elements, use the nsmallest function from heapq to get the smallest element and append it to res.
- Print the res list.
Python3
# Python3 code to demonstrate# Consecutive Subsets Minimum# using heapqimport heapq# initializing listtest_list = [4, 7, 8, 10, 12, 15, 13, 17, 14]# printing original listprint("The original list : " + str(test_list))# using heapq# Consecutive Subsets Minimumres = []for i in range(0, len(test_list), 3): res.append(heapq.nsmallest(1, test_list[i:i+3])[0])# printing resultprint("The grouped minimum list is : " + str(res)) |
The original list : [4, 7, 8, 10, 12, 15, 13, 17, 14] The grouped minimum list is : [4, 10, 13]
Time complexity: O(nlogk), where n is the length of the input list and k is the size of the subset. Here k is 3, so the time complexity is O(nlog3), which can be simplified to O(n).
Space complexity: O(k), where k is the size of the subset. Here k is 3, so the space complexity is O(3), which can be simplified to O(1).
