The challenge

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.

For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

  • 10 = max(10, 5, 2)
  • 7 = max(5, 2, 7)
  • 8 = max(2, 7, 8)
  • 8 = max(7, 8, 7)

Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.

My question

This was posed as a hard coding challenge. My confusion is that I solved the problem in 5 lines of code. Either the code doesn't achieve the correct time complexity (which I think it does), or this challenge has been incorrectly categorised. Please can someone review my code to see if it is correct.

array = [10,5,2,7,8,7,9]
k = 4

for index in range (len(array)-(k-1)):
  • 4
    \$\begingroup\$ Unless I am mistaken, that is O(nk) time, not O(n). Btw, your program works only for k=3. \$\endgroup\$ – Martin R May 26 at 9:55
  • 2
    \$\begingroup\$ Rev 2 is still O(n k) time. \$\endgroup\$ – 200_success May 26 at 12:54
  • \$\begingroup\$ How is this O(nk) time? I thought for loops run in O(n) time and as there are no nested loops this should just be an O(n) time-frame? Why is this not the case? Thanks \$\endgroup\$ – EML May 26 at 20:14
  • 2
    \$\begingroup\$ The max(i:i+k) operation is a nested loop, and runs in O(k), and you perform it n times, making the total time complexity O(n k). \$\endgroup\$ – AJNeufeld May 27 at 1:43
  • \$\begingroup\$ I see. Thank you \$\endgroup\$ – EML May 27 at 9:07

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.