Aditya Verma
patreon
Maximum of all subarrays of size k
🕑 Added 2020-11-16 13:07:11 +0000 UTCComments
Tarun Chaudhary
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
Ahmar Mohammed
Yes, it's not working for [1,3,1,2,0,5]
Shriram Tindivanam Sridharan
yes, it is not working. Do u have a fix fir it ? If so pls share here
Be Legal
doesn't work for [1,3,1,2,0,5] 3
Krishna Prem
Thanks Aditya.. that was great explanation. So it'll be just little more than n, eventually making it the order of n.
Aditya Verma
No, 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.
Krishna Prem
Here 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?
