3
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$ – Adamantoisetortoise Nov 1 '20 at 13:51
  • \$\begingroup\$ I found it: "Min Max Riddle" on Hackerrank \$\endgroup\$ – Adamantoisetortoise Nov 1 '20 at 14:18
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – superb rain Nov 1 '20 at 15:06
  • 2
    \$\begingroup\$ Perhaps add the link to hackerrank in question too. \$\endgroup\$ – hjpotter92 Nov 1 '20 at 15:51
  • \$\begingroup\$ also, check the discussions on the same for a hint on \$ O(n) \$ solution hackerrank.com/challenges/min-max-riddle/forum/comments/486316 \$\endgroup\$ – hjpotter92 Nov 1 '20 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.