Thanks! Very comprehensive explanation. In the third approach using Doubly-LL, I understand that the time complexity is O(N) due to the traversal of the array. Is there no time consumption for the building of DLL. If the elements are coming in descending order, then we have to build the window size right, so wouldn't that make the complexity O(N+K) (K amortized) . Can you elaborate it a bit more on the time complexity arising during the building of DLL and how it impacts the overall complexity.
Thank you! I got 57/61 correct, but kept getting Time limited exceeded for the last 4 test cases. When I tried switching to Priority queue implementation, my correct went down to 49/61, still getting Time Limit exceded. This has been driving me crazy ALL day.
I have watched two of your videos today and I can tell you that the quality of your teaching has increased. Just after understanding both the approaches I felt that I could code on my own and so I did. Thank you very much.
Just honestly one think I didn't like is that with the method fo dequeue: I actually watched the video in order to understand how this method works but you came up with these steps rather than showing the actual way of problem solving and how we can figure out such steps in similar problems. Thank you,
Thanks for your feedback. The logic is similar to maintaing non-decreasing or non-increasing order using stack. We used deque to access from multiple ends.
@@techdose4u Sir can I ask a question? I was also trying to solve it using heap, but I realized that by using heap there's no way I only store Integer in the heap, is this correct? However by using deque, you can store only Integer( index ) in the Deque like your other video. But by heap, is has to be a node but not just a index , right ?
Thank you for the great explanation as usual TECH DOSE. The deque solution does not appear to exactly be O(N). For instance, consider the input: nums = [3, 1, -1, 0, 2, 0, -6, -7] and k = 4. You will notice that you have to pop multiple values (not just one) when you reach index 4. And this can also happen several times in different types of inputs.
@@techdose4u Not really. When maintaining the deque in DSC order, current selected element (right element in k sliding window) need to repeatedly compare to the rear element in this deque, regardless of its data structure being Doubly-LL.
In the heap approach, what is the heap size we should declare. If its n, then the space complexity will be O(n).. Or should we declare the heap of size 2k..? If, we declare heap array of size 2k, then for each heapify, it will take log2k times.. Please clarify once on the heap size what should we declare.. Thanks
This was an amazing video. My question is would it effect the run time if you removed from the heap as you went through the window? I dont believe it would. Also If you use that approach their wouldnt be a need for the index right?
Can you explain why the time complexity for Deque solution is O(n)...are we not count the push operation? The push operation would at worst requires us to traverse through the whole linked list right? So, the worst case of K traversal should be counted. So shouldn't it be O(nk) ??? Please help
I'm not sure that 2nd algorithm is O(N). We traverse list once, correct. But for every position we keep popping elements which are less then current - this is a linear operation too. Am I missing something?
You will push once and pop once (maximum time) for each element. Once an element is pushed and popped then it's never pushed again. So, operations is in order of O(N).
A map implementation is easier than heap implementation.. All elements in map are sorted just like in heap, but popping the leftmost index of window is much easier in map (map[nums[i-k] -= 1)
i just have a doubt like in deque ,method code you have mentioned should we add another for loop before to add the first 3 elements in the vector?or am i missing something?
We can use increase key and decrease key operation ,by comparing elements which are being poped and pushed... if the element that is gng to be pushed greater than popped element we use increase key operation ,if they r equal we do ntg else decrease key operation???
I don't understand how Heap solution has O(n logk)? I think you are loosing the fact that heap removal is taking O(k). So, for each N you will remove item from the heap which will lead to a solution of O(n k).
Two methods solutuon, sliding window and heap from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: return self.heap_method(nums,k) # sliding window is O(N) method i = 0 j = 0 que = deque() ans = [] while j < len(nums): while que and nums[j] > que[-1]: que.pop() que.append(nums[j]) if j-i+1 < k: j+=1 elif j-i+1 == k: ans.append(que[0]) if que[0] == nums[i]: que.popleft() i+=1 j+=1 return ans def heap_method(self,nums,k): # O(NlgK) nums = [-i for i in nums] pq = [(val,idx) for idx,val in enumerate(nums[:k])] heapify(pq) res = [-pq[0][0]] for i in range(k,len(nums)): while pq and pq[0][1]
Hi! What I don't understand is why we still have the (1,0) node in the graph when we moved to the right in the heap solution. I understand it wasn't the max and it didn't affect the result but what if it will over time?
![Summer Walker - Heart Of A Woman [Official Lyric Video]](http://i.ytimg.com/vi/SFddctbZzw8/mqdefault.jpg)
I watched 5 different videos but yours was the only one that helped me finally understand the deque solution. Thank you!
Thanks! Very comprehensive explanation.
In the third approach using Doubly-LL, I understand that the time complexity is O(N) due to the traversal of the array.
Is there no time consumption for the building of DLL. If the elements are coming in descending order, then we have to build the window size right, so wouldn't that make the complexity O(N+K) (K amortized) . Can you elaborate it a bit more on the time complexity arising during the building of DLL and how it impacts the overall complexity.
Thank you! I got 57/61 correct, but kept getting Time limited exceeded for the last 4 test cases. When I tried switching to Priority queue implementation, my correct went down to 49/61, still getting Time Limit exceded. This has been driving me crazy ALL day.
I have watched two of your videos today and I can tell you that the quality of your teaching has increased. Just after understanding both the approaches I felt that I could code on my own and so I did. Thank you very much.
Welcome :) Thanks for the feedback
Brute force: 2:22
Heap: 4:21
Deque: 12:58
Thanks for putting timestamp 😅
all heroes dont wear capes
Just honestly one think I didn't like is that with the method fo dequeue:
I actually watched the video in order to understand how this method works but you came up with these steps rather than showing the actual way of problem solving and how we can figure out such steps in similar problems.
Thank you,
Thanks for your feedback. The logic is similar to maintaing non-decreasing or non-increasing order using stack. We used deque to access from multiple ends.
@@techdose4u would you please help me by suggesting an easier similar problem in order to get a better understanding with this method.
@@ahmadalk2540 easier similar problem can be stock span problem (but that is not window based)
The best video for this leetcode question and it's so easy to follow! THANK YOU!
Thanks :)
The explanation was simply Makkhan ie. Butter..... Hat's off...............
Thanks
Thank you so much Sir! Finally understood it watching the graph you drew. The third solution is so hard to think of..
Nice :)
@@techdose4u Sir can I ask a question? I was also trying to solve it using heap, but I realized that by using heap there's no way I only store Integer in the heap, is this correct? However by using deque, you can store only Integer( index ) in the Deque like your other video. But by heap, is has to be a node but not just a index , right ?
@@yitingg7942 Yes right. Position info is also essential to maintain.
@@techdose4u You replied so fast!! Thank you so much Sir! Happy Lunar New Year!! 🤗😊
Thank you for the great explanation as usual TECH DOSE. The deque solution does not appear to exactly be O(N). For instance, consider the input: nums = [3, 1, -1, 0, 2, 0, -6, -7] and k = 4. You will notice that you have to pop multiple values (not just one) when you reach index 4. And this can also happen several times in different types of inputs.
Every node is pushed and popped exactly once. So, Dequeue time is only O(1).
@@techdose4u Not really. When maintaining the deque in DSC order, current selected element (right element in k sliding window) need to repeatedly compare to the rear element in this deque, regardless of its data structure being Doubly-LL.
In the heap approach, what is the heap size we should declare.
If its n, then the space complexity will be O(n)..
Or should we declare the heap of size 2k..?
If, we declare heap array of size 2k, then for each heapify, it will take log2k times..
Please clarify once on the heap size what should we declare.. Thanks
why to keep index in heap?
because the TC for removal is O(n)
and for push,pop is O(logn)
Thanks a ton for this valuable content!! Top notch explanation.
Thanks :)
This was an amazing video. My question is would it effect the run time if you removed from the heap as you went through the window? I dont believe it would. Also If you use that approach their wouldnt be a need for the index right?
Can you explain why the time complexity for Deque solution is O(n)...are we not count the push operation? The push operation would at worst requires us to traverse through the whole linked list right? So, the worst case of K traversal should be counted. So shouldn't it be O(nk) ??? Please help
The way I see it, at worst case the window is the size of the array, which is why it would be O(n)
Wonderful explanation
Top notch explanation !! thanks for the efforts
Welcome
Amazing Explanation! Thanks a lot....!!
Welcome :)
I'm not sure that 2nd algorithm is O(N). We traverse list once, correct. But for every position we keep popping elements which are less then current - this is a linear operation too.
Am I missing something?
You will push once and pop once (maximum time) for each element. Once an element is pushed and popped then it's never pushed again. So, operations is in order of O(N).
@@techdose4u Thank you for the explanation!
@@DiegoMorales-iy7fw welcome
@@techdose4u This comment has more knowledge than most of the youth. Thank you. It was extremely helpful.
Thanks for clarity was having same doubt
Nice explanation , thank you;
same question has been asked recently in quotient technologies last month....!!!
You are a genius!
😅
A map implementation is easier than heap implementation.. All elements in map are sorted just like in heap, but popping the leftmost index of window is much easier in map (map[nums[i-k] -= 1)
👍🏼
well explained, but you should take pauses when you speak, it is sometimes difficult to follow along as you are talking nonstop
You can pause I guess 😅 otherwise time will increase and hurt the retention time
i just have a doubt like in deque ,method code you have mentioned should we add another for loop before to add the first 3 elements in the vector?or am i missing something?
Thank you so much for such a valuable content
Welcome :)
what is the name of software you use to draw?
I'm grateful. Ty.
Welcome :)
SUBARAAAAASHI exparranasan
We can use increase key and decrease key operation ,by comparing elements which are being poped and pushed... if the element that is gng to be pushed greater than popped element we use increase key operation ,if they r equal we do ntg else decrease key operation???
👍🏼
What is the time complexity of DLL implementation
I don't understand how Heap solution has O(n logk)? I think you are loosing the fact that heap removal is taking O(k). So, for each N you will remove item from the heap which will lead to a solution of O(n k).
@Techdose can you please answer this
Best Explanation!
Not able to access the code links, Error 404..
pls check your all code links
I think instead of using deque only two variables first_maximum and second_maximum are sufficient., do you think that it will work??
I think it wont work that way
Thank you!!
Welcome 😀
Another great explanation. Thanks.
Thank You
Nice explanation
Two methods solutuon, sliding window and heap
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
return self.heap_method(nums,k)
# sliding window is O(N) method
i = 0
j = 0
que = deque()
ans = []
while j < len(nums):
while que and nums[j] > que[-1]:
que.pop()
que.append(nums[j])
if j-i+1 < k:
j+=1
elif j-i+1 == k:
ans.append(que[0])
if que[0] == nums[i]:
que.popleft()
i+=1
j+=1
return ans
def heap_method(self,nums,k):
# O(NlgK)
nums = [-i for i in nums]
pq = [(val,idx) for idx,val in enumerate(nums[:k])]
heapify(pq)
res = [-pq[0][0]]
for i in range(k,len(nums)):
while pq and pq[0][1]
Great explanation!
Thanks
Wonderful explanation..
Great explanation
Thank You Sir..🙏🙏
Welcome :)
thank you sir
Welcome :)
Is it samson qu2 mic?
Do you have the JAVA code?
No
Horrible accent ((( but topic is good
Hi! What I don't understand is why we still have the (1,0) node in the graph when we moved to the right in the heap solution. I understand it wasn't the max and it didn't affect the result but what if it will over time?