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.
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.
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.
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.
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
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.
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???
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)
@@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 ?
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?
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).
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 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?
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]
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).
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?
Brute force: 2:22
Heap: 4:21
Deque: 12:58
Thanks for putting timestamp 😅
all heroes dont wear capes
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 watched 5 different videos but yours was the only one that helped me finally understand the deque solution. Thank you!
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)
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
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.
The best video for this leetcode question and it's so easy to follow! THANK YOU!
Thanks :)
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
The explanation was simply Makkhan ie. Butter..... Hat's off...............
Thanks
why to keep index in heap?
because the TC for removal is O(n)
and for push,pop is O(logn)
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.
same question has been asked recently in quotient technologies last month....!!!
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???
👍🏼
Wonderful explanation
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)
👍🏼
You are a genius!
😅
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!! 🤗😊
Nice explanation , thank you;
Top notch explanation !! thanks for the efforts
Welcome
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?
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
Thanks a ton for this valuable content!! Top notch explanation.
Thanks :)
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)
Amazing Explanation! Thanks a lot....!!
Welcome :)
What is the time complexity of DLL implementation
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
Thank you so much for such a valuable content
Welcome :)
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?
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]
Best Explanation!
Nice explanation
SUBARAAAAASHI exparranasan
I'm grateful. Ty.
Welcome :)
Another great explanation. Thanks.
Thank You
Wonderful explanation..
Thank you!!
Welcome 😀
Great explanation
Great explanation!
Thanks
what is the name of software you use to draw?
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 Sir..🙏🙏
Welcome :)
Not able to access the code links, Error 404..
pls check your all code links
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
thank you sir
Welcome :)
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?
Is it samson qu2 mic?
Do you have the JAVA code?
No
Horrible accent ((( but topic is good