The tricky, and didactic, part of this problem is to store index, rather than value, in the deque- which enables you to tell when the bottom of the deque is outside the window.
this should be a pinned comment....the whole drawing part in the video tells us about storing the number in the deque and in the code you store the index and not telling properly why are you doing that is nothing but a scam...
It can still work even if you store the value. Just pop left when nums[left] == deque[0] (only do this after you append to your output list though). Got my submission to reach 99% faster runtime 😅
Yeah wouldnt been better if he taught it like this tbh, out = [] r,l = 0,0 q = collections.deque() while r < len(nums): while q and q[-1] < nums[r]: q.pop() q.append(nums[r]) if r+1 >= k: out.append(q[0]) if nums[l] == q[0]: q.popleft() l+=1 r+=1 return out
Why you give two sorted array for examples? (1,2,3,4 and later 1,1,1,1,4,5) I found it is very hard to follow when you are using sorted array in the example. Why not use 1, 1, 4, 5, 1, 1 instead so that we can see all cases?
completely agree. The first half of the video makes it sound like the input is sorted. If you already know the problem and solution maybe this is not a big deal, but for someone trying to understand the concept if just makes it a lot more unintuitive and confusing.
agreed, even though the first two examples are meant to show the extra comparisons can be avoided by a deque, he still could have refined the examples and made it a bit more general
The trick of the problem can only be illustrated with a sorted array. The trick is that we don't need need to look at items to the left of the current maximum.
LC solution is not this elegant as yours. Thanks so much! I was getting stuck on this especially the part where we have to start moving left and right together. In the LC solution, they take care of adding the first k element in the deque separately but your approach is simple and works.
Man, I really thank you, is 1:58 of the video and I already solved the problem in my mind, while I am in the toilet after wake up😂, the last two days I did 20 problems and whatched your video to understand the solutions that I did not understand
we know that the leftmost value in the queue is the largest at that point. does this help? I'm confused about this too. did you figure it out? If so, I'd like an explanation please. @NeetCode
I was confused by this too until I noticed his deque contains indexes, not the values themselves. He's comparing the left index to the leftmost index saved in the deque
I was using the values themselves in my code and I was stunned before realizing we are doing things a bit differently class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: l = 0 output = [] q = collections.deque() for r in range(len(nums)): while len(q) != 0 and q[-1] < nums[r]: q.pop() q.append(nums[r]) if r - l + 1 == k: output.append(q[0]) if q[0] == nums[l]: q.popleft() l += 1 return output
'l' represents the beginning index of the current window, and if that has already passed (larger) than the first element in the deque, that would mean the element in deque is out of bound and no longer applicable to the current window
The condition to check whether the window is of the right size or not is incorrect , it should be "(r-l+1)>=k" instead, it worked in your case, but isn't working now, I suppose they have updated the test cases accordingly. Hope it helps someone who might get stuck at this step. Great explanation given none the less
No, it works. The first window ends when r+1 == k. E.g., if k == 2, we should only consider the first 2 elements. In the code after adding those to the deque, the check r+1 == k passes when r == 1. At this time, the front of the deque is put in the output array. Henceforth, r+1 >= k will always remain true as r will increase and at each subsequent next number in the input array a new sliding window forms. First sliding window (l=0,r=1), k=2, next sliding window (l=1,r=2), k=2 etc.
Hi Sir, I wondered why the time complexity is O(n), but not O(nk)? Since we're useing R pointer looping the array takes O N time, and each time takes O K times to check if the new added pointer R number is greater numbers in the queue? Also, the space complexity should be O(k) correct? Since the most elements stored into the queue should be K? We have pop out element once L > q[0], right?
O(n) because we are processing each element twice, once when we add it to the queue and the second time when we remove it from the queue! Space complexity is O(n) because of the output array. It would be O(k) if we disreguard the array
If you're like me and the condition "if l > dq[0]:" confuses you, you can rather use "if dq[0] < (r-k+1):" which makes better sense since we are checking if our window is out of bound by checking the first index of dq and r(current indxex) and k
This is my first hard problem that I solved by myself, I didn't use deque instead kept tracking the currentMaxIndex manually and updating it manually when it goes out of the window, the solution I wrote is pretty inefficient ( beats 9% LOL) but I did it, my first hard problem, here to check how to solve it properly. Thank you for the explanation.
Because line 20 executes before line 15. For example is k = 1, then on the first pass the condition l > q[0] is false because 0 == 0. But we have reached the window size and therefore enter the next conditional statement and increment the startWindow. A better condition for checking the window size is r - l + 1 == k.
I was confused by this too until I noticed his deque contains indexes, not the values themselves. He's comparing the left index to the leftmost index saved in the deque
basically, we are popping the leftmost index stored in the queue because our l is greater than that index. So the leftmost index in the queue is not relevant to the sliding window.
Shouldn't the line 14 be a while loop as we do not pop the leftmost element sometimes (max elem could still be in the range) & sometimes we might have to pop multiples times to compensate for the times we did not pop
how is it not O(n2) , when we have a while loop inside a for loop shouldnt it be o(n * k) n array size and k window size since our deque cant have more values than k , since we keep on popping the deque shouldnt it be o(n*k)
Lets assume that I take the following approach, I have a left pointer, a right pointer and a variable maxValue to keep track of the maximum value of the window. Whenever I move the window, if the upcoming value (i.e nums[right]) is greater than the maxValue then I will simply update the maxValue with the new value. Whereas if the maxValue lies in the left end of the window then after moving the window, The value of maxValue won't be available in the new window (It would be at index left-1) so I'd have to iterate through the window and find out the maxValue. I can skip this iteration if I could somehow store the values in decreasing order. So even if maxValue goes out of window I'll still have the successive values in decreasing order. I hope this would help.
About the time complexity, we know that each element is added and removed once. I was thinking about the number of comparisons we need when I realize every comparison generates a result: if current number is smaller or deque is empty, add current element to the deque, else remove rightmost element. So the total number of comparisons is equal to the number of insertion and deletion.
Could someone explain me on O(K * (n - k)) at @2:04? Using the provided example, there are n = 8 and k = 3 which would yield 15 using the complexity algorithm. However, the maximum window is only 6 so I am super confused. Please note that my experience is very little
This problem breaks the common misconception that the window in the sliding window always have to be an array/vector/list, which is not true, look at it, it's a double ended queue, aka. deque!
Sliding Window Approach with Monotonic Queue : The idea is to keep the maximum number in the sliding window at the front of the Deque and the possible maximum numbers at the rear end (last) of the queue. The Deque would have numbers sorted in descending order, front having the maximum number and rear would have the smallest in the current window. As we iterate over the array if num[i] is greater than the smallest number of current window than we start removing the numbers as long as num[i] is greater than number in the window. Also we add the index of current number in Deque as this number could be possible maximum as the window slides to the right. We could have tried to use Stack or PriorityQueue to keep track of maximum in the current window, but we don't only need to track maximum number in the current window but also other numbers (possible maximum) which are less than maximum number in the current window. Because as we move to the next window, these possible maximum numbers might become the maximum number in that window. Choosing the right Data Structure : Double Ended Queue (Deque) If we use Stack, we can only get access to the top element, for accessing other elements we would have to pop the elements from the stack and would have to push it back to stack. Similarly if we use PriorityQueue we can only get access to the min or max element which is at the top of heap, for accessing other elements we would have to remove elements from the heap and would have to push it back to heap. A Double ended Queue allows us to perform operation on both the ends of the data structure and we can easily access the elements in Deque. We could have used Doubly Linked List as well but the problem is, it lacks the ease of access to perform operation or access elements from both the front and rear end. In Java Deque gives us methods e.g. addFirst(), addLast(), removeFirst(), removeLast(), peekFirst(), peekLast() to easily access the front/rear element and also start traversal from the front or rear. Important Points : We store the index i in Deque and not num[i], this is because we also have to remove numbers from the Deque as window slides to the right. We can check if index is out of current window we remove the number. For given window of K, remember we don't try to store k elements in the Deque, rather we just need to keep the maximum number at the front of Deque and add the current number at the rear end of Deque. And when we remove element from Deque we start from the rear end of Deque.
(r + l) >= k - 1 since the indexing starts from 0. I don't know how this code was submitted successfully but I couldn't. While tracing, I realized (r + l) >= k - 1 and my code works pretty fine now. Edit: Changed (r + l) to (r - l), still seemed to work pretty well.
In the example with 1s, 4 and 5, what if 4 was in position 1 of the array? How would the deque keep track of when 4 goes out of bounds in the window ? If the purpose of the deque is to keep track of the position within the window, we would need to keep track of the max and not just use the left most in the deque?
we are maintaining the deque in such a way that left is max and right is min How? when we are about to push an element, we remove all the smaller ones(two reasons : 1. when we find a greater element, the smaller ones are never gonna be max so they are useless 2.When we remove the smaller ones from the right, and then put the current element the rightmost one is still the smallest now) try drawing the deque in a paper and you will get it this is kind of like the pattern search algo, just that we need deque for its functions
Great explanation!! But how can we know when to pop and when not to from the start of the array. In the first example we don't pop from the left while in the 2nd one we did pop from the left??
In the drawing solution part, you are adding the elements while in the code you are storing the indices of the elements in the deque. Is there a reason?
There's a small correction in the code if (r + (l+1)) >= k: res.append(nums[q[0]]) l += 1 We should be checking (r + (l+1)) >= k because for (l = 0, r = 2) 2 >= 3 will not satisfy for k = 3
I think it's because when you go from index -> length we increment by 1. So when we compare r (which is an index) to k (which is a length) to make a comparison r needs to be incremented by 1
That's there only for the first time. In the first iteration you are starting with l and r both equal to 0 So you skip the if condition until r < k But when r becomes >=k it means we have reached to the point where our sliding window is full with size = k Now it's implied that in each of the next iterations our sliding window will always be full with size = k So, in each iteration we add the max element to the output array
I made some minor modifications which make the logic a little easier to understand. In particular, I appended the current pointer at the top of the loop, and then shift (popleft) the pointers to smaller items from the head. #-------------------- from collections import deque def sliding_window_maximum(nums, k): output = [] # deque allows us to shift (popleft) in O(1) time # in the queue, we are going to store the index (pointer) to the nums # array such that the values are decreasing (the head points to the # greatest value) q = deque() # l = left index of the window l = 0 # the right window pointer is the next value being processed # loop all items to be processed for r, value in enumerate(nums): # increment l after at least k items have been processed if r > k -1: l += 1 q.append(r) # to keep the queue in decreasing order, the head must be # greater than the value just added while q and nums[q[0]] < value: q.popleft() # remove pointers in the queue that are before the current window # position if q[0] < l: q.popleft() # after the right window index is at least k, we start adding # the greatest value in the window to the output if r >= k - 1: output.append(nums[q[0]]) return output # added the -4 to the input so code to check the left pointer is executed print(sliding_window_maximum([1, 3, -1, -3, -4, 5, 3, 6, 7], 3)) # [3, 3, -1, 5, 5, 6, 7]
Does the company logo in the thumbnail of each video indicate that the problem was asked before in an interview with that company? For example, for this video it is more likely to be asked in a Google interview?
This is a simpler algorithm. However, max(nums[w:w+k]) requires O(k) work, and you run it O(n) times, so the runtime is O(n*k). Suppose n = 1,000,000 and k = 2,500. Now, if you double the window size to k = 5,000. Now you're maxing 5,000 elements per window slice, so it will run 2x slower. In @NeetCode's solution, increasing the window size *doesn't* increase the runtime at all! That's what justifies the more complicated solution.
Solved using both max heap and queue class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # i,j = 0,0 # max_heap = [] # res= [] # while j < len(nums): # # removing all prev added samller num compare to the curr_num # while max_heap and -max_heap[-1] < nums[j]: # max_heap.pop() # # add the curr_num into heap # heapq.heappush(max_heap, -nums[j]) # # reached the window of size k # if j-i+1 == k: # # add the max in element in the windows size of k # max_num = -max_heap[0] # res.append(max_num) # if max_num == nums[i]: # heapq.heappop(max_heap) # i+=1 # j+=1 # return res i,j = 0,0 res = [] queue = deque() while j < len(nums): # queue's monotonic dc order breaks while queue and queue[-1] < nums[j]: queue.pop() queue.append(nums[j]) if j-i+1 == k: max_num = queue[0] res.append(max_num) if max_num == nums[i]: queue.popleft() i+=1 j+=1 return res
My solution that passes on LC: I feel as this is more consistant with the way neetcode solved the other ones. Exact same algo class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q = deque() l = 0 res = [] for r in range(len(nums)): while len(q) != 0 and nums[r] > nums[q[-1]]: # pop all smaller elements from queue q.pop() q.append(r) if r - l + 1 == k: res.append(nums[q[0]]) if r - l + 1 > k: l += 1 while q[0] < l: q.popleft() res.append(nums[q[0]]) return res
i have looked into leetcode discussions section and everywhere possible to understand what exactly the following line does while d and nums[d[-1]] < nums[r]: d.pop() nobody properly explains what it even does and why its necessary, not even this video.
I have a question, why the time O(n) ? I thought it would be something like O(nk) cuz when we do popping out from the deque, wouldn't that cause some additional time as well?
Can someone please explain why the while loop to clear and add in the deque will not increase the time complexity . I think so my basic concept on this complexity computation are wrong . Can please anyone dumb it down for me
Maximum number of elements you can remove from the queue is the same as the maximum that can be added. The amount that can be added is O(n), so the while loop is O(n).
I find the drawn explanations SERIOUSLY lacking (also compared to all your other videos) and I'll explain why. Only the coding part is where anything began to make any sense or answer any of the questions at all. Even after the coding part though I was left wondering "Why are we even doing it like this?" because the drawn explanations were so bad and insufficient. Here are my first-viewing initial questions watching this drawn explanation around 5:25: 1) If the deque is the size of the window (okay, seems intuitively like it could make sense), why are we popping everything out of it reducing the size to the single largest number? What does this even tell us? Why did the size matter? Why (not when) are you popping (it's unexplained)? 2) When we look at the next window (or just next number), how are we making sure that 4 wasn't a part of the window that we're NOT looking at any longer (the first number of the last window)? You don't cover this at all, you just say "Compare the 5 and remove the 4 since it's larger" 7:02. That's mostly unhelpful and just perplexing 3) You also say the queue is "always decreasing" but what does that even mean? You don't explain that, and all I can see is it's not decreasing numerically as it's going 1,1,1,1,4,5 by the happenstance of your problem set (it's increasing). In fact, it doesn't seem to contain more than one number ever (as mentioned above). As you start the next drawn explanation: 1) At 8:49 you draw an arrow to the "beginning" at the right side.... and then draw an arrow to the "beginning" on the left side. 😑😵💫 2) You say at 10:14 "Okay the first thing to notice is the 8 is no longer in bounds so we have to pop". HOW DO WE KNOW THAT!?! We literally didn't even add the smaller numbers that might have been before it so we have absolutely no idea where the 8 actually stood because the dequeue doesn't represent position of the window at all. 🤯 The 8 could have been the 3rd index (or any other), and still totally be within our window 😑 The drawn explanations here serve purely as wheels of confusion and raising unanswered and unsolved questions.
from typing import List import collections class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: """ Find the maximum sliding window in an array of integers. Args: nums (List[int]): The input array of integers. k (int): The size of the sliding window. Returns: List[int]: The list containing the maximum values in each sliding window. Example: Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Output: [3, 3, 5, 5, 6, 7] """ q, res = collections.deque(), [] # Use a deque for efficient operations.
# Iterate through the array from left to right. for r in range(len(nums)): # Remove smaller elements from the deque. while q and nums[r] > nums[q[-1]]: q.pop()
# Add the current index to the deque. q.append(r)
# Check if the window has enough elements. if r + 1 < k: continue
# Check if the leftmost element is outside the window [r+1-k, r], remove it from the deque. # checking if the index at q[0] is smaller than left = r+1-k, if it is then just pop the index at left if q[0] < (r + 1 - k): q.popleft()
# Append the maximum value in the current window to the result list. res.append(nums[q[0]])
The trick used to store indices was not intuitive at all for me. So, I tried to tweak it to store the numbers instead: class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: que = deque([]) res = [] l,r = 0, 0 for r in range(len(nums)): while que and nums[r] > que[-1]: que.pop() que.append(nums[r]) if r-l+1 == k: res.append(que[0]) if nums[l] == que[0]: que.popleft() l += 1 return res
My guess is in python stack is implemented based on array where popleft requires left-shift of each element taking O(n), and the deque works like a double linked list where popleft is just delete the leftmost node, which is O(1)
i'm currently new to this, and i'm confused. Can anyone tell me why when looking at this problem, we could think of deque and solution like this, like, is there any pattern or smth like that ?
I solved this with the naive way within like 10 minutes, but then watched your video and looked around solutions and chatGPT to study the optimal solution but I could not understand it when i was walking through the code I was keep losing track of the logic. I gave up and went to bed and next morning gave it another shot on pen and papper approach until i figured it out. I hope I dont get these kind of questions on my interviews cuz this can be disheartening and draining
Honestly, the way you solved this problem is rather confusing for me. I solved it similar to Maximum Sum Subarray Of Size k to help me understand the pattern and this is how I solved it: class Solution { public int[] maxSlidingWindow(int[] nums, int k) { Deque q = new LinkedList(); ArrayList sol = new ArrayList(); int left = 0; for (int right = 0; right < nums.length; right++) { while (!q.isEmpty() && nums[right] > nums[q.getLast()]) { q.removeLast(); } q.add(right); if (right - left + 1 == k) { sol.add(nums[q.getFirst()]); left++; if (q.getFirst() < left) { q.removeFirst(); } } } int[] ans = new int[sol.size()]; for (int i = 0; i < sol.size(); i++) { ans[i] = sol.get(i); } return ans; } }
thanks! Can someone pls tell me why lines 14 exist ? i.e. if l > q[0]: q.popleft() . I understand the q.popleft but just not able to understand the 'if' statement preceding it. thanks so much!
Am I the only one who thought to use a binary search tree (multiset in C++) on their first try? The time complexity of this approach O(n log k), worse than the deque solution which is O(n). However the BST solution worked within the time limit.
went through the solution 4 times and then understood...theres no chance that someone will come up with the solution in the interview round.....unless someone has seen neetcodes video
Your code has while loop inside while loop and you claim it is O(n)? I think it's O(n*k) which is worse than if you use a size k heap which is O(n*logk)
Find it a bit confusing to use two pointers, l and r, both of which increment 1 each time. Since this is a fixed window, it make more sense just to have one right pointer.
This not space efficient: Space complexity is worse case scenario O(n) Here is a more efficient solution space-wise (and yes there another solution both space and time wise most effecient, you have to find it) So: in pseudo code i =0, j=K; List res; max_idx = max_element(arr(i), arr(j)); res.push(arr(max_idx)); While(j < arr.size()) { ++i; ++j; if(arr(max_idx) > arr(j)) { if(i>max_idx) { max_idx = max_element (arr(i),arr(j)); res.push(arr(max_idx)); continue; } res.push(arr(max_idx)); } else { max_idx = j; res.push(arr(max_idx)); } }
Instead of storing the whole window, we store a decreasing sequence of elements from the window. The usual way to build a decreasing sequence is to scan left-to-right and accept any lesser element. For example, if the window is 6 5 4 1 2 3, then we obtain 6 5 4 1. But that's NOT what we do. Instead, we scan *right-to-left* and accept any *greater* element. This way, we obtain 6 5 4 3.
@@aaronhanson1694 Suppose the input is [1,2,3,4,5,6] and k = 3. The windows are [1,2,3], [2,3,4], [3,4,5], and [4,5,6]. Instead of storing the complete window, we store a decreasing sequence, as described above. In this example, we store [3], [4], [5], and [6]. It's actually the simplest case, and it works fine.
The tricky, and didactic, part of this problem is to store index, rather than value, in the deque- which enables you to tell when the bottom of the deque is outside the window.
this should be a pinned comment....the whole drawing part in the video tells us about storing the number in the deque and in the code you store the index and not telling properly why are you doing that is nothing but a scam...
It can still work even if you store the value. Just pop left when nums[left] == deque[0] (only do this after you append to your output list though). Got my submission to reach 99% faster runtime 😅
like the other commentor said - no need for index.
Yeah wouldnt been better if he taught it like this tbh,
out = []
r,l = 0,0
q = collections.deque()
while r < len(nums):
while q and q[-1] < nums[r]:
q.pop()
q.append(nums[r])
if r+1 >= k:
out.append(q[0])
if nums[l] == q[0]:
q.popleft()
l+=1
r+=1
return out
Best Solution, less indices to track
Why you give two sorted array for examples? (1,2,3,4 and later 1,1,1,1,4,5) I found it is very hard to follow when you are using sorted array in the example. Why not use 1, 1, 4, 5, 1, 1 instead so that we can see all cases?
He gave an unsorted array example at the end (8:26) as well. [8, 7, 6, 9]
completely agree. The first half of the video makes it sound like the input is sorted. If you already know the problem and solution maybe this is not a big deal, but for someone trying to understand the concept if just makes it a lot more unintuitive and confusing.
agreed, even though the first two examples are meant to show the extra comparisons can be avoided by a deque, he still could have refined the examples and made it a bit more general
@piyo1231 this code fails for [1,3,-1,-3,5,3,6,7] window 3. Check once and give sol
The trick of the problem can only be illustrated with a sorted array. The trick is that we don't need need to look at items to the left of the current maximum.
the best part is even if I figure out the solution after struggling, I still come to see your explanation because it's just so beautiful
FACTS!
Factos
Finally, the monotonic queue data structure makes sense!!! Thank you
LC solution is not this elegant as yours. Thanks so much! I was getting stuck on this especially the part where we have to start moving left and right together. In the LC solution, they take care of adding the first k element in the deque separately but your approach is simple and works.
Very cool! Now I am curious to try and apply this data structure to other problems 🤔
I was wondering why it was so easy to figure out at first. Good thing I decided to head here after implementing the brute force solution.
Thanks! Small suggestion: `l` can just be `r - k + 1`, which will still do the right thing for the first k elements where it is negative.
What does that do for us besides obviating one line (i.e. the `l = 0` initialization line)?
This is very helpful, thanks so much for sharing it!!
Thanks, happy it was helpful 🙂
Man, I really thank you, is 1:58 of the video and I already solved the problem in my mind, while I am in the toilet after wake up😂, the last two days I did 20 problems and whatched your video to understand the solutions that I did not understand
Always the best, thank you, Neet! I watched your video 3 times to understand the problem.
Thank you NeetCode for this video. I am able to identify the redundancies in the ccalculations of maximum. The use of a deque is genius
You have simplified it so well!
@neetcode, in line #14, if l > q[0], why are we comparing left index to leftmost value in the queue? shouldn't it be value at the left index?
we know that the leftmost value in the queue is the largest at that point. does this help? I'm confused about this too. did you figure it out? If so, I'd like an explanation please. @NeetCode
I was confused by this too until I noticed his deque contains indexes, not the values themselves. He's comparing the left index to the leftmost index saved in the deque
@@shavitl.306 ^^^
I was using the values themselves in my code and I was stunned before realizing we are doing things a bit differently
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
l = 0
output = []
q = collections.deque()
for r in range(len(nums)):
while len(q) != 0 and q[-1] < nums[r]:
q.pop()
q.append(nums[r])
if r - l + 1 == k:
output.append(q[0])
if q[0] == nums[l]:
q.popleft()
l += 1
return output
'l' represents the beginning index of the current window, and if that has already passed (larger) than the first element in the deque, that would mean the element in deque is out of bound and no longer applicable to the current window
i must say guys i am not getting this at all surprisingly i am just blank
The condition to check whether the window is of the right size or not is incorrect , it should be "(r-l+1)>=k" instead, it worked in your case, but isn't working now, I suppose they have updated the test cases accordingly. Hope it helps someone who might get stuck at this step. Great explanation given none the less
No, it works. The first window ends when r+1 == k. E.g., if k == 2, we should only consider the first 2 elements. In the code after adding those to the deque, the check r+1 == k passes when r == 1. At this time, the front of the deque is put in the output array. Henceforth, r+1 >= k will always remain true as r will increase and at each subsequent next number in the input array a new sliding window forms. First sliding window (l=0,r=1), k=2, next sliding window (l=1,r=2), k=2 etc.
@@charleskorey6515I see.. so as it's a fixed sized window we don't need to do r - l + 1 every time, r+1 works just as well!
Hi Sir, I wondered why the time complexity is O(n), but not O(nk)? Since we're useing R pointer looping the array takes O N time, and each time takes O K times to check if the new added pointer R number is greater numbers in the queue?
Also, the space complexity should be O(k) correct? Since the most elements stored into the queue should be K? We have pop out element once L > q[0], right?
O(n) because we are processing each element twice, once when we add it to the queue and the second time when we remove it from the queue! Space complexity is O(n) because of the output array. It would be O(k) if we disreguard the array
@@avipatel1534 I think when asking about space complexity, it's always asking about extra space?
4:21 DJ Khaled!!
If you're like me and the condition "if l > dq[0]:" confuses you, you can rather use "if dq[0] < (r-k+1):" which makes better sense since we are checking if our window is out of bound by checking the first index of dq and r(current indxex) and k
This is my first hard problem that I solved by myself, I didn't use deque instead kept tracking the currentMaxIndex manually and updating it manually when it goes out of the window, the solution I wrote is pretty inefficient ( beats 9% LOL) but I did it, my first hard problem, here to check how to solve it properly. Thank you for the explanation.
100%, I dont know why he went with this convoluted solution. Just maintain the max within the window and you only search beyond that max.
quick question, I believe the last if statement should be if(r-left+1)>=k, right? because we are calculating the window size
To select my teacher going forward, I watched all the videos explaining this problem #239. Your explanation is the best by far. Thank you!
how many viedos was taht total
This is a very clear solution. One comment: The if condition should have (r+l)> = k-1 as the indexing is from o.
When does l > q[0] encountered?? basically when do we popleft? I think we should popleft when l == q[0]. Can you please confirm? @neetcode
Because line 20 executes before line 15. For example is k = 1, then on the first pass the condition l > q[0] is false because 0 == 0. But we have reached the window size and therefore enter the next conditional statement and increment the startWindow. A better condition for checking the window size is r - l + 1 == k.
I was confused by this too until I noticed his deque contains indexes, not the values themselves. He's comparing the left index to the leftmost index saved in the deque
basically, we are popping the leftmost index stored in the queue because our l is greater than that index. So the leftmost index in the queue is not relevant to the sliding window.
Shouldn't the line 14 be a while loop as we do not pop the leftmost element sometimes (max elem could still be in the range) & sometimes we might have to pop multiples times to compensate for the times we did not pop
how is it not O(n2) , when we have a while loop inside a for loop shouldnt it be o(n * k) n array size and k window size since our deque cant have more values than k , since we keep on popping the deque shouldnt it be o(n*k)
good explanation for monotonically decreasing dequeue method
many thanks
DJ Khaled been real quiet since 4:20 dropped...
I do understand solution but where do u get the basic intuation that this can be solved vai monotonic DS?
Lets assume that I take the following approach, I have a left pointer, a right pointer and a variable maxValue to keep track of the maximum value of the window.
Whenever I move the window, if the upcoming value (i.e nums[right]) is greater than the maxValue then I will simply update the maxValue with the new value.
Whereas if the maxValue lies in the left end of the window then after moving the window, The value of maxValue won't be available in the new window (It would be at index left-1) so I'd have to iterate through the window and find out the maxValue.
I can skip this iteration if I could somehow store the values in decreasing order. So even if maxValue goes out of window I'll still have the successive values in decreasing order.
I hope this would help.
About the time complexity, we know that each element is added and removed once. I was thinking about the number of comparisons we need when I realize every comparison generates a result: if current number is smaller or deque is empty, add current element to the deque, else remove rightmost element. So the total number of comparisons is equal to the number of insertion and deletion.
Since insertion and deletion is O(N), comparison is O(N), added together still O(N)
@@linli7049 can you elaborate. one would need to compare k times at each number, leading to a runtime of N*K right?
@@propropropropuser exactly what I was thinking. How can it be O(n)?
Could someone explain me on O(K * (n - k)) at @2:04?
Using the provided example, there are n = 8 and k = 3 which would yield 15 using the complexity algorithm. However, the maximum window is only 6 so I am super confused.
Please note that my experience is very little
It should be O(k * (n - k + 1)) because there are (n - k + 1) windows.
This problem breaks the common misconception that the window in the sliding window always have to be an array/vector/list, which is not true, look at it, it's a double ended queue, aka. deque!
Sliding Window Approach with Monotonic Queue :
The idea is to keep the maximum number in the sliding window at the front of the Deque and the possible maximum numbers at the rear end (last) of the queue. The Deque would have numbers sorted in descending order, front having the maximum number and rear would have the smallest in the current window.
As we iterate over the array if num[i] is greater than the smallest number of current window than we start removing the numbers as long as num[i] is greater than number in the window.
Also we add the index of current number in Deque as this number could be possible maximum as the window slides to the right.
We could have tried to use Stack or PriorityQueue to keep track of maximum in the current window, but we don't only need to track maximum number in the current window but also other numbers (possible maximum) which are less than maximum number in the current window. Because as we move to the next window, these possible maximum numbers might become the maximum number in that window.
Choosing the right Data Structure : Double Ended Queue (Deque)
If we use Stack, we can only get access to the top element, for accessing other elements we would have to pop the elements from the stack and would have to push it back to stack.
Similarly if we use PriorityQueue we can only get access to the min or max element which is at the top of heap, for accessing other elements we would have to remove elements from the heap and would have to push it back to heap.
A Double ended Queue allows us to perform operation on both the ends of the data structure and we can easily access the elements in Deque. We could have used Doubly Linked List as well but the problem is, it lacks the ease of access to perform operation or access elements from both the front and rear end. In Java Deque gives us methods e.g. addFirst(), addLast(), removeFirst(), removeLast(), peekFirst(), peekLast() to easily access the front/rear element and also start traversal from the front or rear.
Important Points :
We store the index i in Deque and not num[i], this is because we also have to remove numbers from the Deque as window slides to the right. We can check if index is out of current window we remove the number.
For given window of K, remember we don't try to store k elements in the Deque, rather we just need to keep the maximum number at the front of Deque and add the current number at the rear end of Deque. And when we remove element from Deque we start from the rear end of Deque.
thank you! one step closer to MS
Hi, May I know what gadget you are using for drawing ? Wanted to buy something like this but not sure which one will appreciate the help.
(r + l) >= k - 1 since the indexing starts from 0. I don't know how this code was submitted successfully but I couldn't. While tracing, I realized (r + l) >= k - 1 and my code works pretty fine now.
Edit: Changed (r + l) to (r - l), still seemed to work pretty well.
Thank you for your explanation. This is a great help!
4:20 DJ Khaled's competitor found
lol
Thank you. That was a great explanation👍
This is so nicely explained. thank you
In the example with 1s, 4 and 5, what if 4 was in position 1 of the array? How would the deque keep track of when 4 goes out of bounds in the window ? If the purpose of the deque is to keep track of the position within the window, we would need to keep track of the max and not just use the left most in the deque?
yeah dude i swear to god on every neetcode video I have 1 burning question that he never addresses. It's honestly starting to piss me off
Explanation doesn't cover these things which is a bit annoying.
thank you for the great explanation! super helpful.
from your explaination, you stored the value in q, then why use q.append(r) instead of q.append(nums[r]). Why storing the indices
Why is it o(n) if you're having the inner while loop?
Doesn't "pop smaller element from queue take O(k) time? in the worst case, you have to look at every element in the queue?
we are maintaining the deque in such a way that left is max and right is min
How?
when we are about to push an element, we remove all the smaller ones(two reasons : 1. when we find a greater element, the smaller ones are never gonna be max so they are useless 2.When we remove the smaller ones from the right, and then put the current element the rightmost one is still the smallest now)
try drawing the deque in a paper and you will get it
this is kind of like the pattern search algo, just that we need deque for its functions
i had same question but apparently deque is constant on both sides lol
Great explanation!! But how can we know when to pop and when not to from the start of the array. In the first example we don't pop from the left while in the 2nd one we did pop from the left??
You need to maintain a left pointer and keep checking if left > queue most left element as we have to update window while moving to right.
Can you explain the O(n) DP sol, where we divide the array in blocks of k and calculate max_left and max_right ?
Thanks mate ! It really helps!
Should we not use the max heap?
Using (right - left + 1) % k == 0 over right + 1 >= k would have made the code more intuitive and readable IMO. Nice explanation though.
Please share your code
Great hit, also can just do (right - left + 1) == k is fine.
@@gladyouseen8160 just need change that line 17 condition in the video.
im confused bc in order for the algorithm to work the array has to be sorted right?
In the drawing solution part, you are adding the elements while in the code you are storing the indices of the elements in the deque. Is there a reason?
There's a small correction in the code
if (r + (l+1)) >= k:
res.append(nums[q[0]])
l += 1
We should be checking (r + (l+1)) >= k because for (l = 0, r = 2) 2 >= 3 will not satisfy for k = 3
Hi, I am confused about the part we check for the size of the window, why R + 1 >= k ?
I think it's because when you go from index -> length we increment by 1. So when we compare r (which is an index) to k (which is a length) to make a comparison r needs to be incremented by 1
That's there only for the first time.
In the first iteration you are starting with l and r both equal to 0
So you skip the if condition until r < k
But when r becomes >=k it means we have reached to the point where our sliding window is full with size = k
Now it's implied that in each of the next iterations our sliding window will always be full with size = k
So, in each iteration we add the max element to the output array
u can also do (r-l + 1) == k
I made some minor modifications which make the logic a little easier to understand. In particular, I appended the current pointer at the top of the loop, and then shift (popleft) the pointers to smaller items from the head.
#--------------------
from collections import deque
def sliding_window_maximum(nums, k):
output = []
# deque allows us to shift (popleft) in O(1) time
# in the queue, we are going to store the index (pointer) to the nums
# array such that the values are decreasing (the head points to the
# greatest value)
q = deque()
# l = left index of the window
l = 0
# the right window pointer is the next value being processed
# loop all items to be processed
for r, value in enumerate(nums):
# increment l after at least k items have been processed
if r > k -1:
l += 1
q.append(r)
# to keep the queue in decreasing order, the head must be
# greater than the value just added
while q and nums[q[0]] < value:
q.popleft()
# remove pointers in the queue that are before the current window
# position
if q[0] < l:
q.popleft()
# after the right window index is at least k, we start adding
# the greatest value in the window to the output
if r >= k - 1:
output.append(nums[q[0]])
return output
# added the -4 to the input so code to check the left pointer is executed
print(sliding_window_maximum([1, 3, -1, -3, -4, 5, 3, 6, 7], 3))
# [3, 3, -1, 5, 5, 6, 7]
Does the company logo in the thumbnail of each video indicate that the problem was asked before in an interview with that company? For example, for this video it is more likely to be asked in a Google interview?
"Does the company logo in the thumbnail of each video indicate that the problem was asked before in an interview with that company?" Yes
Maybe double linked list with head and tail pointers, this trick of deque is aweful (O(1) pop and popleft). After that, the solution is valid
Thanks @NeetCode! That's really useful.
Isn't below more simple solution?
class Solution:
def sumOfSlidingWindow(self, nums: List[int], k : int) -> List[int]:
output = []
for w in range(len(nums)-k+1):
output.append(max(nums[w:w+k]))
# 1,3,-1,-3,5,3,6,7
return output
This is a simpler algorithm.
However, max(nums[w:w+k]) requires O(k) work, and you run it O(n) times, so the runtime is O(n*k).
Suppose n = 1,000,000 and k = 2,500. Now, if you double the window size to k = 5,000. Now you're maxing 5,000 elements per window slice, so it will run 2x slower.
In @NeetCode's solution, increasing the window size *doesn't* increase the runtime at all! That's what justifies the more complicated solution.
Solved using both max heap and queue
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# i,j = 0,0
# max_heap = []
# res= []
# while j < len(nums):
# # removing all prev added samller num compare to the curr_num
# while max_heap and -max_heap[-1] < nums[j]:
# max_heap.pop()
# # add the curr_num into heap
# heapq.heappush(max_heap, -nums[j])
# # reached the window of size k
# if j-i+1 == k:
# # add the max in element in the windows size of k
# max_num = -max_heap[0]
# res.append(max_num)
# if max_num == nums[i]:
# heapq.heappop(max_heap)
# i+=1
# j+=1
# return res
i,j = 0,0
res = []
queue = deque()
while j < len(nums):
# queue's monotonic dc order breaks
while queue and queue[-1] < nums[j]:
queue.pop()
queue.append(nums[j])
if j-i+1 == k:
max_num = queue[0]
res.append(max_num)
if max_num == nums[i]:
queue.popleft()
i+=1
j+=1
return res
ur my time hero again!
My solution that passes on LC:
I feel as this is more consistant with the way neetcode solved the other ones. Exact same algo
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
l = 0
res = []
for r in range(len(nums)):
while len(q) != 0 and nums[r] > nums[q[-1]]:
# pop all smaller elements from queue
q.pop()
q.append(r)
if r - l + 1 == k:
res.append(nums[q[0]])
if r - l + 1 > k:
l += 1
while q[0] < l:
q.popleft()
res.append(nums[q[0]])
return res
Thank you, this was really helpful!
very nice and clear explanation actually, thank you :)
i have looked into leetcode discussions section and everywhere possible to understand what exactly the following line does
while d and nums[d[-1]] < nums[r]:
d.pop()
nobody properly explains what it even does and why its necessary, not even this video.
I have a question, why the time O(n) ? I thought it would be something like O(nk) cuz when we do popping out from the deque, wouldn't that cause some additional time as well?
O(N)+O(N)=O(N)
Can someone please explain why the while loop to clear and add in the deque will not increase the time complexity . I think so my basic concept on this complexity computation are wrong . Can please anyone dumb it down for me
Maximum number of elements you can remove from the queue is the same as the maximum that can be added. The amount that can be added is O(n), so the while loop is O(n).
I find the drawn explanations SERIOUSLY lacking (also compared to all your other videos) and I'll explain why. Only the coding part is where anything began to make any sense or answer any of the questions at all. Even after the coding part though I was left wondering "Why are we even doing it like this?" because the drawn explanations were so bad and insufficient.
Here are my first-viewing initial questions watching this drawn explanation around 5:25: 1) If the deque is the size of the window (okay, seems intuitively like it could make sense), why are we popping everything out of it reducing the size to the single largest number? What does this even tell us? Why did the size matter? Why (not when) are you popping (it's unexplained)? 2) When we look at the next window (or just next number), how are we making sure that 4 wasn't a part of the window that we're NOT looking at any longer (the first number of the last window)? You don't cover this at all, you just say "Compare the 5 and remove the 4 since it's larger" 7:02. That's mostly unhelpful and just perplexing 3) You also say the queue is "always decreasing" but what does that even mean? You don't explain that, and all I can see is it's not decreasing numerically as it's going 1,1,1,1,4,5 by the happenstance of your problem set (it's increasing). In fact, it doesn't seem to contain more than one number ever (as mentioned above).
As you start the next drawn explanation: 1) At 8:49 you draw an arrow to the "beginning" at the right side.... and then draw an arrow to the "beginning" on the left side. 😑😵💫 2) You say at 10:14 "Okay the first thing to notice is the 8 is no longer in bounds so we have to pop". HOW DO WE KNOW THAT!?! We literally didn't even add the smaller numbers that might have been before it so we have absolutely no idea where the 8 actually stood because the dequeue doesn't represent position of the window at all. 🤯 The 8 could have been the 3rd index (or any other), and still totally be within our window 😑
The drawn explanations here serve purely as wheels of confusion and raising unanswered and unsolved questions.
Your videos are the best
from typing import List
import collections
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
"""
Find the maximum sliding window in an array of integers.
Args:
nums (List[int]): The input array of integers.
k (int): The size of the sliding window.
Returns:
List[int]: The list containing the maximum values in each sliding window.
Example:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
"""
q, res = collections.deque(), [] # Use a deque for efficient operations.
# Iterate through the array from left to right.
for r in range(len(nums)):
# Remove smaller elements from the deque.
while q and nums[r] > nums[q[-1]]:
q.pop()
# Add the current index to the deque.
q.append(r)
# Check if the window has enough elements.
if r + 1 < k:
continue
# Check if the leftmost element is outside the window [r+1-k, r], remove it from the deque.
# checking if the index at q[0] is smaller than left = r+1-k, if it is then just pop the index at left
if q[0] < (r + 1 - k):
q.popleft()
# Append the maximum value in the current window to the result list.
res.append(nums[q[0]])
return res
Will it be linear if we use heap and keep on adding the new element in the window to heap and getting maximum element from heap .
nah i think that'd be nlogk
How is this O(n); one would need to compare k times at each number, leading to a runtime of N*K right?
The trick used to store indices was not intuitive at all for me. So, I tried to tweak it to store the numbers instead:
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = deque([])
res = []
l,r = 0, 0
for r in range(len(nums)):
while que and nums[r] > que[-1]:
que.pop()
que.append(nums[r])
if r-l+1 == k:
res.append(que[0])
if nums[l] == que[0]:
que.popleft()
l += 1
return res
I am a little confused since you pop and add element from the same side of the queue, does the queue function the same as a stack?
My guess is in python stack is implemented based on array where popleft requires left-shift of each element taking O(n), and the deque works like a double linked list where popleft is just delete the leftmost node, which is O(1)
In python, deque is used for queue. In C++, we have queue, stack and deque
thank you NeetCode god!
i'm currently new to this, and i'm confused. Can anyone tell me why when looking at this problem, we could think of deque and solution like this, like, is there any pattern or smth like that ?
Thanks for the awesome explanation
I solved this with the naive way within like 10 minutes, but then watched your video and looked around solutions and chatGPT to study the optimal solution but I could not understand it when i was walking through the code I was keep losing track of the logic. I gave up and went to bed and next morning gave it another shot on pen and papper approach until i figured it out. I hope I dont get these kind of questions on my interviews cuz this can be disheartening and draining
Very clear. Thanks!
No problem, thanks for watching!
I see that there are nested (while) loops in the solution. How come it's O(n)?
i found this can be solved without using a deque rather an array/vector with left counter. if possible make a video on that.
thankx
why "if l>q[0]"? I feel it can only be "l
Honestly, the way you solved this problem is rather confusing for me. I solved it similar to Maximum Sum Subarray Of Size k to help me understand the pattern and this is how I solved it:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque q = new LinkedList();
ArrayList sol = new ArrayList();
int left = 0;
for (int right = 0; right < nums.length; right++) {
while (!q.isEmpty() && nums[right] > nums[q.getLast()]) {
q.removeLast();
}
q.add(right);
if (right - left + 1 == k) {
sol.add(nums[q.getFirst()]);
left++;
if (q.getFirst() < left) {
q.removeFirst();
}
}
}
int[] ans = new int[sol.size()];
for (int i = 0; i < sol.size(); i++) {
ans[i] = sol.get(i);
}
return ans;
}
}
This makes more sense to me.
thanks! Can someone pls tell me why lines 14 exist ? i.e. if l > q[0]: q.popleft() . I understand the q.popleft but just not able to understand the 'if' statement preceding it. thanks so much!
Got it now. I missed they were indices and was thinking them of as values somehow.
if l > q[0]:
q.popleft()
did not understand this part. Can anyone explain as if I understand nothing?
oh I got it
if not l
Very helpful video ❤️
Thanks! :)
Clever solution!
Am I the only one who thought to use a binary search tree (multiset in C++) on their first try? The time complexity of this approach O(n log k), worse than the deque solution which is O(n). However the BST solution worked within the time limit.
great explanation thank you
c++ solution
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int i=0;
int j=0;
vector res;
deque q;
while(j
good work!!!
You are the best!
went through the solution 4 times and then understood...theres no chance that someone will come up with the solution in the interview round.....unless someone has seen neetcodes video
Your code has while loop inside while loop and you claim it is O(n)? I think it's O(n*k) which is worse than if you use a size k heap which is O(n*logk)
Ok, as I researched yesterday on sliding window topic, this problem doesn't seem Hard by I have doubts, it should be hard..
Find it a bit confusing to use two pointers, l and r, both of which increment 1 each time. Since this is a fixed window, it make more sense just to have one right pointer.
I agree with you. I think it's convention to have two pointers in sliding window problems, but in cases like this it's easier to have one pointer.
I agree.
Is this monotonic queue method directly applicable for LC739. Daily Temperatures? Edit: saw it here: ua-cam.com/video/cTBiBSnjO3c/v-deo.html
I was trying to solve using stack/queue, until I saw this video to realize we need to use deque here.
This not space efficient:
Space complexity is worse case scenario O(n)
Here is a more efficient solution space-wise (and yes there another solution both space and time wise most effecient, you have to find it)
So: in pseudo code
i =0, j=K;
List res;
max_idx = max_element(arr(i), arr(j));
res.push(arr(max_idx));
While(j < arr.size())
{
++i; ++j;
if(arr(max_idx) > arr(j))
{
if(i>max_idx)
{
max_idx = max_element (arr(i),arr(j));
res.push(arr(max_idx));
continue;
}
res.push(arr(max_idx));
}
else
{
max_idx = j;
res.push(arr(max_idx));
}
}
Instead of storing the whole window, we store a decreasing sequence of elements from the window. The usual way to build a decreasing sequence is to scan left-to-right and accept any lesser element. For example, if the window is 6 5 4 1 2 3, then we obtain 6 5 4 1. But that's NOT what we do. Instead, we scan *right-to-left* and accept any *greater* element. This way, we obtain 6 5 4 3.
I don't think this would work if we had an input of all increasing numbers.
@@aaronhanson1694 Suppose the input is [1,2,3,4,5,6] and k = 3. The windows are [1,2,3], [2,3,4], [3,4,5], and [4,5,6]. Instead of storing the complete window, we store a decreasing sequence, as described above. In this example, we store [3], [4], [5], and [6]. It's actually the simplest case, and it works fine.
Thank you for this solution. But I believe there's a minor bug, the r +=1 update should happen before the l+r >=k check.
no bro, u have to move r pointer everytime