Maximum of all subarrays of size k
Added 2020-11-16 13:07:11 +0000 UTCComments
Working code from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: start = 0 end = 0 q = deque() ans = [] while end < len(nums): while len(q) > 0 and q[-1] < nums[end]: q.pop() q.append(nums[end]) if end-start+1 < k: end += 1 elif end - start + 1 == k: ans.append(q[0]) if nums[start] == q[0]: q.popleft() start += 1 end += 1 return ans
Tarun Chaudhary
2024-08-06 00:01:25 +0000 UTCYes, it's not working for [1,3,1,2,0,5]
Ahmar Mohammed
2022-07-17 16:30:00 +0000 UTCyes, it is not working. Do u have a fix fir it ? If so pls share here
Shriram Tindivanam Sridharan
2021-02-03 07:25:56 +0000 UTCdoesn't work for [1,3,1,2,0,5] 3
Be Legal
2021-01-15 05:22:11 +0000 UTCThanks Aditya.. that was great explanation. So it'll be just little more than n, eventually making it the order of n.
Krishna Prem
2021-01-02 06:49:00 +0000 UTCNo, not at all ! Brute force is actually O(n^2), let's understand what order of n^2 means => Usually it means for every n elements it should run n times right? eg: if we have 5 elements, for the first element it will run 5 times, then for second element it will run 5 times and then for the third. fourth and fifth as well. Or its increasing with every element, like 1 time for first, 2 times for second and so on. (without any if conditions) Now lets take a moment to understand if thats happening in our solution? Q1: Does it run n times ? (n=size of the array) Q2: Does it run for every n elements in the array? I think you should have gotten the answer by now. While someone can argue its appears to be a little extra than just order of n, but if you see carefully we are far far away from order of n^2. So it will still count as Order of n. Remember this: If there is something evaluating inside a condition and that condition ifsnot getting executed everytime, It wont be order of n^2. Well that being the general logical explanation of why its not order of n^2, but you can always do rigorous time complexity analysis to find out the truth yourself :D Btw in interviews, just having a general idea of TC for your solution is more than enough. Nobody asks you to derive it. But if you're still confused, you should do it.
Aditya Verma
2021-01-02 05:25:29 +0000 UTCHere you are using a While Loop for popping the elements in the list till they are greater than the 'j'th does'nt that increase the time complexity again and make it equal to brute force?
Krishna Prem
2020-12-30 12:44:54 +0000 UTC
