# Find the max value between minimum values in sub-arrays

I have an array of integers, I have to find all sub-arrays of different size from 1 to len(array). In every sub-array, I have to find the minimum value in it, once done I have to find the maximum value between the minimum values of all the subarrays of the same size. Finally, I have to return these maximum values in a list.

So the first value in my list will always be the maximum integer in the array, the second value will be the maximum between the minimum values of the sub-arrays size 2, and so on; the last value in the list will always be the minimum integer of the array. Original problem here: Min Max Riddle

def min_max_subarrays(arr):
result = [max(arr), ]
w = 2
while w < len(arr):
temp = 0
for i, n in enumerate(arr[:-w+1]):
x = min(arr[i:i+w])
if x > temp:
temp = x
result.append(temp)
w += 1
result.append(min(arr))
return result


The function is correct but I'm sure there's a way to reduce time complexity. I feel one loop is unnecessary but I'm struggling to find a way to remove it.

• I corrected the indentation (It was a copy/paste error), yes it is online somewhere but I did it a while ago and don't remember where it is... If my explanation isn't clear I can search for the original. – Adamantoisetortoise Nov 1 '20 at 13:51
• I found it: "Min Max Riddle" on Hackerrank – Adamantoisetortoise Nov 1 '20 at 14:18
• I see. So one important thing you omitted is the limits. n=10^6 rules out not only cubic time solutions like yours but also quadratic time ones. – superb rain Nov 1 '20 at 15:06
• Perhaps add the link to hackerrank in question too. – hjpotter92 Nov 1 '20 at 15:51
• also, check the discussions on the same for a hint on $O(n)$ solution hackerrank.com/challenges/min-max-riddle/forum/comments/486316 – hjpotter92 Nov 1 '20 at 15:55