nice explanation but I have a question, why are we deleting from the back ( pop_back() ) instead we can delete from the front also then we can use queue
I am glad someone asked this Qn. Just do a dry run on this example : [1,3,1,2,0,5], K = 3 queue = {1} queue = {3} ----> 3 popped element 1 from front because 3 > 1 queue = {3, 1} queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, Since we have deque, we can delete 1 which is < 2. I wish I had explained this example as well in the video. Thank you so much @herculean6748 ❤
I wholeheartedly request you to please never think to stop making videos bhaiya , Trust me we all are learning just because of you. Your explanations are unmatchable. ❤️
no one can teach like you. No offence to NeetCode, striver or any other famous youTubers, this guy is on another level of making things simple to the ground. I don't understand how he does this. #augustchallengewithMIK
No one covers these 19:19 You are the only one I have noticed stressing in these minute details like which DS to use, why Deque used etc. You are a true master.
?????????? If someone is wondering why I didn't use a simple queue ??????? Just do a dry run on this simple example : [1,3,1,2,0,5], K = 3 queue = {1} queue = {3} ----> 3 popped element 1 from front because 3 > 1 queue = {3, 1} queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could delete 1 which is < 2. Hope this helps. Special thanks to @herculean6748 for asking this qn.
My JAVA CODE - class Solution { public int[] maxSlidingWindow(int[] nums, int k) { // story points // 1. when new element comes,make space for it (window size can't exceed k) // 2. when nums[i] comes,there is no need to keep small elements in that window,pop them; // 3. now push i in deque-> for nums[i] // 4. if(i>=k-1),then deque.front() is our answer for that window int n=nums.length; int x=0; Deque deque = new ArrayDeque(); int[] res=new int[n-k+1]; for(int i=0;i=k-1){ res[x++]=nums[deque.getFirst()]; } } return res; } }
Been trying to share your content with friends and classmates as much as possible, i just want to help your channel to grow and would love to see more people appreciating your efforts. You're a gem MIK sir❤️
🚨🚨🚨ALERT - This was asked again by Media.net yesterday in 1st round of interview (16th Aug, 2023)🚨🚨🚨 iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-239-Sliding%20Window%20Mazimum.pdf ******* Similar Problem ******* (Use same 4 Steps method) Leetcode - 1425 - Constrained Subsequence Sum - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Constrained%20Subsequence%20Sum.cpp ******************** JAVA CODE ******************** class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDeque q = new ArrayDeque(); int i=0, j=0, ptr=0; int n = nums.length; int[] res = new int[n-k+1]; while(j
Tedx Talk is on the way bro! I guess if you keep posting regular videos, very soon you would cover every question of LeetCode, and then 2 yrs down the line, you will be called for a Ted Talk. "Jo bhi question Leetcode pe milega, vo yahan samjhate huye tumhe main dikhega"
Wow. I am so happy it was clear to you all. This is one of the most important sub-topics of sliding window and many many tough qns can be solved using this 4 step process. Just write these 4-step and do a simple dry run and see what extra thing need to be done. That’s it ❤️😇🙏🙏🙏
pls sir never stop posting and keep videos like this separated by playlist. Just finished this sliding window playlist. Had a problem with the hard question as u discussed but i will try to watch it again
and sir i am really having a hard time understanding back-tracking solutions. Any tips u can give?? I have watched max of ur Dp playlist videos and becoz of that i could solve many question like wordbreak problem Longest Increasing subsequence by myself but backtracing giving me very hard time🥲🥲😰
hey mik, can you explain " minimum number of multiplications to reach end " it is a problem on gfg based on graph but at first it seems like a dp problem it would be good if you explain this
@@codestorywithMIK ok, let me see and tell. Btw I need that recur to bottom up vid cuz CSES mein recur wala code most of the time TLE de rha h (frustrating) but bottom up accept ho rha h.
Python code : class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q = deque() ans = [] for i in range(len(nums)): while q and nums[q[-1]] < nums[i]: q.pop() while q and i - q[0] >= k : q.popleft() q.append(i) if i >= k-1 : ans.append(nums[q[0]]) return ans
I understand that u cannot launch a batch right now sir but can u please atleast make a guidance video on which topic wise questions to solve from ur channel after completing a particular topic... Starting from arrays... Because as beginner we cannot solve array+dp mix question in starting right... Pls we want a guided path..
Thank you for making awesome video like this!! if possible ,can you please add English subtitle or explain in English ,that would definitely attract more views
Maine Heap se kara tha , uska time complexity O(n.log(n)) hai and space O(n) . But your solution , hey bhagwaan . Kaha se laate ho bhaiya aisa dimaag . Please tell how to think for this kind of approach . How to think like this .
Hi mik, in this case of maximum in each subarray, you can even pop from the last the elements which are equal to current element right? Because even if they are removed, the current same element will be there in window for even the next windows where it can be maximum again.
I did tried it by myself like for 5-6 hour even more, tried map got tle Then i got intuition that we are going to do it by max heap did tried but got failed.then watched your solution and got my mistake just i was writing if inside of while loop if(top.second
Hey MIK hope your are doing absolutely fine these days.. when can you take some questions?? I just want you to discuss some questions on weekends as per audience want once or twice a week.. just a suggestion 😢
BF . Class solution { Public int[]Max sliding windows (int nums [],int k){ int n=nums. length; if(n==0||k==0){ return new int nums (0); } int nums of window=n-k+1; int[]res=nums [nums of window]; for(int start=0;start nums [i2]-nums[i1])); for(int i=0;i0){ max pq.remove(start) } max pq.offer (i); if(max pq.size()==k; res(i-k+1)=nums [max pq.peek()); } } return res; } }; 3rd approach. public int max sliding window(int[]nums,int k){ int n=nums. length; if(n==0||k==0){ return new int (0); } int[]res = nums (n-k+1); dequeuedq=new Array dequeue(); for(int i=0;i0&&dq.peek first ()0&&nums (dq.peek last())=k-1){ res [i-k+1]=nums (dq.peek first ()); } } return res 1st approach Tc =n*k 2nd approach Tc=nlogk. 3rd approach Tc (n); thanks again
Thank you MIK!! ❤ My Java Solution: class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDeque q = new ArrayDeque(); int i=0, j=0, ptr=0; int n = nums.length; int[] res = new int[n-k+1]; while(j
Hii Bhaiya I have one doubt, many a times iIhave seen people saying that you should learn basics first , what does this mean, do we have to know implementation of everything Like for example I know what priority_queue is,what its property, like what happens in min heap or maxheap. So it is sufficient in long run or do i have understand the implementation of each topics , like what happens behind the scene
ALWAYS ALWAYS, understand the implementation as well. It helps you understand the internal working and you also get to know what operations take what time complexity. For example : maxHeapify is O(n) , but why ? This can only be cleared if one is aware of how it is implemented internally. I was asked to implement min-heap once in an interview
Hey MIK I tried the question named 132 pattern I found it tricky and struggled to get the optimal solution.. can you write the approach how to think ..it's obvs that you have mentioned that it falls under monotonic stack/queue based problem but how to frame the solution in this question
Brute Optimal TLE, but all test cases passed, class Solution { // Sliding-Window, TC: O(n*k) public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = new int[n - k + 1]; // Initialize max to the maximum element in the first window int max = Integer.MIN_VALUE; for (int i = 0; i < k; i++) { max = Math.max(max, nums[i]); } res[0] = max; // Iterate through the rest of the array for (int i = 1; i
?????????? If someone is wondering why I didn't use a simple queue ??????? Just do a dry run on this simple example : [1,3,1,2,0,5], K = 3 queue = {1} queue = {3} ----> 3 popped element 1 from front because 3 > 1 queue = {3, 1} queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could delete 1 which is < 2. Hope this helps.
No it will not work. Just do a dry run on this simple example : [1,3,1,2,0,5], K = 3 queue = {1} queue = {3} ----> 3 popped element 1 from front because 3 > 1 queue = {3, 1} queue = {3, 1} -> Now, 2 came and if you pop from front , you won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could pop 1 which is < 2. Hope this helps.
For Freshers and 1-2 years of experience - ruclips.net/p/PLpIkg8OmuX-KiAbBKuNidN-c66aHwBh3t Candidates with >= 2 to 5 years experience - ruclips.net/p/PLpIkg8OmuX-KrStViqRAIJV6MXej-tNy4
nice explanation but I have a question, why are we deleting from the back ( pop_back() ) instead we can delete from the front also then we can use queue
I am glad someone asked this Qn.
Just do a dry run on this example :
[1,3,1,2,0,5], K = 3
queue = {1}
queue = {3} ----> 3 popped element 1 from front because 3 > 1
queue = {3, 1}
queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, Since we have deque, we can delete 1 which is < 2.
I wish I had explained this example as well in the video.
Thank you so much @herculean6748 ❤
@@codestorywithMIK now it is crystal clear, thanks!!
Can you pin this comment...it will be really helpful for others also ...I had to find it after going through all the comments
@ankitshaw_3060 done ❤️❤️
Thanks❤
I wholeheartedly request you to please never think to stop making videos bhaiya , Trust me we all are learning just because of you. Your explanations are unmatchable. ❤️
Hi @GeniusOG,
This means everything to me.
Thank you so much and I will never stop posting.
Love and respect ❤️❤️❤️❤️
hey how did you get that Rs. 40 tag in your comment ?
Can you tell me, I also want to reward this legend
click on three dots just right after like and share button and there you will find an option for thanks, use that.@@Momentsofmagic28
no one can teach like you. No offence to NeetCode, striver or any other famous youTubers,
this guy is on another level of making things simple to the ground. I don't understand how he does this.
#augustchallengewithMIK
No one covers these 19:19
You are the only one I have noticed stressing in these minute details like which DS to use, why Deque used etc.
You are a true master.
?????????? If someone is wondering why I didn't use a simple queue ???????
Just do a dry run on this simple example :
[1,3,1,2,0,5], K = 3
queue = {1}
queue = {3} ----> 3 popped element 1 from front because 3 > 1
queue = {3, 1}
queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could delete 1 which is < 2.
Hope this helps.
Special thanks to @herculean6748 for asking this qn.
Thanks a lot
My JAVA CODE -
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// story points
// 1. when new element comes,make space for it (window size can't exceed k)
// 2. when nums[i] comes,there is no need to keep small elements in that window,pop them;
// 3. now push i in deque-> for nums[i]
// 4. if(i>=k-1),then deque.front() is our answer for that window
int n=nums.length;
int x=0;
Deque deque = new ArrayDeque();
int[] res=new int[n-k+1];
for(int i=0;i=k-1){
res[x++]=nums[deque.getFirst()];
}
}
return res;
}
}
Been trying to share your content with friends and classmates as much as possible, i just want to help your channel to grow and would love to see more people appreciating your efforts. You're a gem MIK sir❤️
Much appreciated Shubham.
Thank you so much for this ❤️❤️❤️
me too
this is one of my favorite problem good explanation. i was struggling so much dequeue approach past now i understood very well
Thank you so much.
My favourite too
🚨🚨🚨ALERT - This was asked again by Media.net yesterday in 1st round of interview (16th Aug, 2023)🚨🚨🚨
iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-239-Sliding%20Window%20Mazimum.pdf
******* Similar Problem ******* (Use same 4 Steps method)
Leetcode - 1425 - Constrained Subsequence Sum - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Constrained%20Subsequence%20Sum.cpp
******************** JAVA CODE ********************
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque q = new ArrayDeque();
int i=0, j=0, ptr=0;
int n = nums.length;
int[] res = new int[n-k+1];
while(j
Your every explanation gives me a confidence that I can solve such type of questions… thank you sooo much 🙌
Tedx Talk is on the way bro!
I guess if you keep posting regular videos, very soon you would cover every question of LeetCode, and then 2 yrs down the line, you will be called for a Ted Talk.
"Jo bhi question Leetcode pe milega, vo yahan samjhate huye tumhe main dikhega"
Totally agree with this. I think my college is already planning to call him and Apna-College for their some small ted talk. Not sure.
true
Means a lot ❤️
Superb and the only best solution I found for this problem. You have explained why duque is used. Thanks a lot
I wish I could like this video a million times.
superb explaination bro thanks so much bro for regularaly giving this beautiful content,🥰🥰🥰😍😍😘
Wow.
I am so happy it was clear to you all.
This is one of the most important sub-topics of sliding window and many many tough qns can be solved using this 4 step process.
Just write these 4-step and do a simple dry run and see what extra thing need to be done. That’s it ❤️😇🙏🙏🙏
pls sir never stop posting and keep videos like this separated by playlist. Just finished this sliding window playlist. Had a problem with the hard question as u discussed but i will try to watch it again
Sure thing.
Means a lot to me Pratyush for trusting my small channel. ❤️❤️😇
and sir i am really having a hard time understanding back-tracking solutions. Any tips u can give?? I have watched max of ur Dp playlist videos and becoz of that i could solve many question like wordbreak problem Longest Increasing subsequence by myself but backtracing giving me very hard time🥲🥲😰
hey mik, can you explain " minimum number of multiplications to reach end " it is a problem on gfg based on graph but at first it seems like a dp problem it would be good if you explain this
Hi there,
Can you please share Qn link ❤️
bhaiya your efforts for all of these videos are just next level
Was waiting for this!
Means a lot.
Since today is a very important video, I would love to know if it was explained well.
Thank you 🙏
@@codestorywithMIK I completely understood the story. Thanks a lot ! You never disappoint.
Thank you 😇😇🙏🙏
Best channel on RUclips for dsa
Hi Shivam.
It means a lot to me.
Thank you so so much ❤️😇🙏
💯
100% true
Thanks Bhaiya for amazing explaination #story_to_code
Ek specific video bna denge chota Sa jisme aap recur+memo ko bottom up mein convert krna sikha dein 🙏
I will surely cover that in my "DP Concepts & Qns" Playlist
Also, since today, this is a very important video, I would love to know if it was explained well.
Thank you 🙏
@@codestorywithMIK ok, let me see and tell. Btw I need that recur to bottom up vid cuz CSES mein recur wala code most of the time TLE de rha h (frustrating) but bottom up accept ho rha h.
@@codestorywithMIKbeautifully explained sir. Let me see if I am able to solve the description wala ques now. Thnx ❤❤
bhaiya yaar kya samjhaya aapne matlab gajab 🔥🔥🔥🔥🔥🔥
superb explanation
I solved this by using priority queue + hashing technique.
Wonderful 😇💪
can you please upload the video solution of weekly contest of leetcode as well? it will be helpful a lot.
Please consider making videos on segment tree problems on leetcode.
your way of explanation is awesome.🤠🤠
Thank you 😇❤️
Python code :
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
ans = []
for i in range(len(nums)):
while q and nums[q[-1]] < nums[i]:
q.pop()
while q and i - q[0] >= k :
q.popleft()
q.append(i)
if i >= k-1 :
ans.append(nums[q[0]])
return ans
Thanks a lot 😇🙏
thanks for python
I understand that u cannot launch a batch right now sir but can u please atleast make a guidance video on which topic wise questions to solve from ur channel after completing a particular topic...
Starting from arrays...
Because as beginner we cannot solve array+dp mix question in starting right...
Pls we want a guided path..
Sure thing Tejaswi
How about I make a video this Weekend on that ?
@@codestorywithMIK yes sir pls make that video
@@codestorywithMIK yes sir pls make it ASAP.. It will be very helpful
❤️❤️ thanks for osm explanation
Amazing explanation
Thank you for making awesome video like this!! if possible ,can you please add English subtitle or explain in English ,that would definitely attract more views
Maine Heap se kara tha , uska time complexity O(n.log(n)) hai and space O(n) . But your solution , hey bhagwaan .
Kaha se laate ho bhaiya aisa dimaag .
Please tell how to think for this kind of approach . How to think like this .
Amazing explaination.. Bhaiya, can you please make a video upon constrained subsequence sum. Wo thoda difficult ho rha hai. It would be a great help.
Sure noted ❤️😇
Thanks Sir 🙏
Hi mik, in this case of maximum in each subarray, you can even pop from the last the elements which are equal to current element right? Because even if they are removed, the current same element will be there in window for even the next windows where it can be maximum again.
great explanation ! thanks!
Thank you ❤️🙏😇
good explanation man!
I did tried it by myself like for 5-6 hour even more, tried map got tle
Then i got intuition that we are going to do it by max heap did tried but got failed.then watched your solution and got my mistake just i was writing if inside of while loop if(top.second
OP content
cfbr
Hey MIK hope your are doing absolutely fine these days.. when can you take some questions?? I just want you to discuss some questions on weekends as per audience want once or twice a week.. just a suggestion 😢
Let me share an excel sheet soon and you guys can fill in the problems there ok
BF .
Class solution {
Public int[]Max sliding windows (int nums [],int k){
int n=nums. length;
if(n==0||k==0){
return new int nums (0);
}
int nums of window=n-k+1;
int[]res=nums [nums of window];
for(int start=0;start nums [i2]-nums[i1]));
for(int i=0;i0){
max pq.remove(start)
}
max pq.offer (i);
if(max pq.size()==k;
res(i-k+1)=nums [max pq.peek());
} }
return res;
}
};
3rd approach.
public int max sliding window(int[]nums,int k){
int n=nums. length;
if(n==0||k==0){
return new int (0);
}
int[]res = nums (n-k+1);
dequeuedq=new Array dequeue();
for(int i=0;i0&&dq.peek first ()0&&nums (dq.peek last())=k-1){
res [i-k+1]=nums (dq.peek first ());
}
}
return res
1st approach Tc =n*k
2nd approach Tc=nlogk.
3rd approach Tc
(n);
thanks again
Thank you MIK!! ❤
My Java Solution:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque q = new ArrayDeque();
int i=0, j=0, ptr=0;
int n = nums.length;
int[] res = new int[n-k+1];
while(j
Thank you so much for java ❤❤❤
Thanks a lot for java bro
Thank you sir! Awesome explanation
Most welcome! 😇❤️
Finally it's here
Means a lot.
Since today is a very important video, I would love to know if it was explained well.
Thank you 🙏
Awesome as always
Hii Bhaiya I have one doubt, many a times iIhave seen people saying that you should learn basics first , what does this mean, do we have to know implementation of everything
Like for example I know what priority_queue is,what its property, like what happens in min heap or maxheap.
So it is sufficient in long run or do i have understand the implementation of each topics , like what happens behind the scene
ALWAYS ALWAYS, understand the implementation as well. It helps you understand the internal working and you also get to know what operations take what time complexity.
For example : maxHeapify is O(n) , but why ?
This can only be cleared if one is aware of how it is implemented internally.
I was asked to implement min-heap once in an interview
thank you :)
You're welcome 😇🙏
u explained it so well❤
Thanks
Thank you 🙏 😇
Great Video 👌🏻
Thank you 😇
Bhai contest k hard questions bhi krwa dia kro bhut buda solutions hote h aapke please
Hey MIK I tried the question named 132 pattern I found it tricky and struggled to get the optimal solution.. can you write the approach how to think ..it's obvs that you have mentioned that it falls under monotonic stack/queue based problem but how to frame the solution in this question
Sure noted. Let me plan a video on that ❤️❤️
can we solve by storing number itself in deque not storing index .i tried this way but i get stucked to manage window size
Leetcode Contest mein hard question dekhkar lagta hai, nahi hoga, ye toh. Please make a video on it
CAN U RECOMMENED SOME MORE DECREASING DEQUE CUZ MOST OF THE TIME ITS INCREASINGN
Some qns based on Monotonic Decreasing -
leetcode.com/problems/daily-temperatures/
leetcode.com/problems/132-pattern/
Brute Optimal TLE, but all test cases passed,
class Solution { // Sliding-Window, TC: O(n*k)
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
// Initialize max to the maximum element in the first window
int max = Integer.MIN_VALUE;
for (int i = 0; i < k; i++) {
max = Math.max(max, nums[i]);
}
res[0] = max;
// Iterate through the rest of the array
for (int i = 1; i
Awesome ❤️❤️❤️
why the window idx >= k-1 and not idx == k?
Nice explanation
Thank you 😇🙏
Bhaiya kya app iPad ke notes upload kar sakate ho revision ke lie
Started attaching from today onwards.
Today’s Leetcode POTD will have PDF Link attached in the Description of the video
why deque is used instead of queue?pls explain
?????????? If someone is wondering why I didn't use a simple queue ???????
Just do a dry run on this simple example :
[1,3,1,2,0,5], K = 3
queue = {1}
queue = {3} ----> 3 popped element 1 from front because 3 > 1
queue = {3, 1}
queue = {3, 1} -> Now, 2 came and since we can only pop from front in queue, we won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could delete 1 which is < 2.
Hope this helps.
❤❤
Means a lot.
Since today is a very important video, I would love to know if it was explained well.
Thank you 🙏
Best explanation bro. I haven't understood why people are using dequeue but you made it very clear thank you ❤
Means a lot.
Thank you so much.
I will make another video soon on why priority queue can also be used to solve this ❤️😇🙏
Thank you 😊👏
Thank you so much for watching 😇🙏
humne peeche se hi kyun delete kiya... i think aage se bhi delete krne se accept hona chahiye ?
No it will not work.
Just do a dry run on this simple example :
[1,3,1,2,0,5], K = 3
queue = {1}
queue = {3} ----> 3 popped element 1 from front because 3 > 1
queue = {3, 1}
queue = {3, 1} -> Now, 2 came and if you pop from front , you won't be able to pop 3 because 3 > 2. This is the catch, if we had taken deque, we could pop 1 which is < 2.
Hope this helps.
thanks it makes sense it is now clear to me.@@codestorywithMIK
bro and pls make a video on hoe system design in important or interviews and hot to start and some tips on system design .
For Freshers and 1-2 years of experience - ruclips.net/p/PLpIkg8OmuX-KiAbBKuNidN-c66aHwBh3t
Candidates with >= 2 to 5 years experience - ruclips.net/p/PLpIkg8OmuX-KrStViqRAIJV6MXej-tNy4
thanks so much bro.❤@@codestorywithMIK
16/31 #augustchallengewithMIK
Sir i solved it using set, is it fine??
vector maxSlidingWindow(vector& nums, int k) {
sets;
for(int i=0; i
Wow. this is good bro.
did this question before but forgot it
Everyone forgets. It’s alright.
Keep revisiting concepts. It will help a lot 😇🙏
Browser me dark mode use karo 😂
Sure 😇❤️