Find the maximum value between minimum values in sub-arrays

Question

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.

• superb rain: 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.
• hjpotter92: also, check the discussions on the same for a hint on \$ O(n) \$ solution hackerrank.com/challenges/min-max-riddle/forum/comments/486316
• Zachary Vance: By 'the maximum between' do you mean 'the maximum OF' or 'the maximum of the pairwise subtraction'?
• Adamantoisetortoise: "the maximum of", also there's a link with all the details

Answer 1

Documentation

The PEP 8 style guide recommends adding docstrings for functions. The name of the function is a little vague.

def min_max_subarrays(arr):
 """
 In an array of integers, find all sub-arrays of different size
 from 1 to the length of the array.
 Add more details...
 """

The docstring should specify the type of the input and the return type. It should also include a description of the algorithm.

Naming

The input variable arr would be more descriptive as integers. It is common practice to use plurals for arrays. Similarly for result; results would be better.

The variables named w, x and temp convey no meaning. If they are meant to represent integers from the input array, they could have more meaningful names like current_min.

Simpler

The variable named n is unused:

for i, n in enumerate(arr[:-w+1]):

Typically, the underscore placeholder is used:

for i, _ in enumerate(arr[:-w+1]):

This expression:

-w+1

is simpler as:

1-w

Efficiency

Instead of repeatedly executing len:

while w < len(arr):

you could execute it once and assign it to a variable:

number_of_ints = len(arr)
while w < number_of_ints:

This might speed up the code.

Comments

It would be beneficial to add some comments to the code. For example, you could explain this line:

w = 2

You could describe what w represents and why you chose the number 2.

Layout

The code uses inconsistent indentation. The black program can be used to automatically format the code for consistency.

• Stef: "The docstring should specify the type of the input and the return type" << But that function accepts any sliceable collection, such as list or tuple or numpy.array, as long as the elements of that collection can be compared with eachother. That doesn't seem like an easy thing to describe by type in python.
• toolic: @Stef: The question states "I have an array of integers". My answer merely points out that it would be helpful to users and maintainers of the code that the docstring should contain that information. If the code author also intends for the function to support other array types, then stating so in the docstring would also be helpful.