Sliding Window Maximum | Monotonic Deque | INTUITIVE | GOOGLE | Leetcode-239 | Dry Run
Вставка
- Опубліковано 9 лют 2025
- ****** Similar Problem ******
Leetcode - 1425 - Constrained Subsequence Sum - github.com/MAZ...
iPad PDF Notes - github.com/MAZ...
This is the 12th Video on our Sliding Window Playlist.
In this video we will try to solve a very popular Sliding Window Problem "Sliding Window Maximum" (Leetcode - 239)
Trust me, this will no longer be a Hard Problem. I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Sliding Window Maximum
Company Tags : Google, Zenefits, Microsoft, Zoho, Flipkart, Amazon, Directi, SAP Labs
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
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.@@FanIQQuiz
@@FanIQQuiz Use thanks option of video
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
?????????? 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
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.
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🥲🥲😰
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
how was this better than striver's explanation???? crazy way of teaching bro!
🚨🚨🚨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
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
I wish I could like this video a million times.
Best channel on UA-cam for dsa
Hi Shivam.
It means a lot to me.
Thank you so so much ❤️😇🙏
💯
100% true
Your every explanation gives me a confidence that I can solve such type of questions… thank you sooo much 🙌
Superb and the only best solution I found for this problem. You have explained why duque is used. Thanks a lot
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 ❤️😇🙏🙏🙏
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 😇😇🙏🙏
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;
}
}
bhaiya yaar kya samjhaya aapne matlab gajab 🔥🔥🔥🔥🔥🔥
Your segment tree videos were so helpful that when I returned back to this problem, I instantly realised this question can be solved by Segment Trees as well. This question is exactly same as Range Maximum, queries being ith index to i+kth index
why deque is used:
1)Efficient removal from both ends: Deque allows us to remove outdated indices (from the front) and smaller elements (from the back).
2)Maintaining maximum efficiently: Deque ensures that the front always holds the index of the maximum element for the current window.
3)Optimal time complexity: The deque helps achieve O(n) time complexity, whereas using a normal queue would be much less efficient.
👍🏻♥️
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 ❤️
your way of explanation is awesome.🤠🤠
Thank you 😇❤️
superb explanation
Great Video 👌🏻
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
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 ❤️
Please consider making videos on segment tree problems on leetcode.
can you please upload the video solution of weekly contest of leetcode as well? it will be helpful a lot.
Amazing explanation
I solved this by using priority queue + hashing technique.
Wonderful 😇💪
very nice explaination 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.
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 ❤❤
Awesome as always
Thanks Sir 🙏
❤️❤️ thanks for osm explanation
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
Thank you sir! Awesome explanation
Most welcome! 😇❤️
can we solve by storing number itself in deque not storing index .i tried this way but i get stucked to manage window size
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 ❤️😇
u explained it so well❤
Thanks
Thank you 🙏 😇
Amazing explaination !!
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
great explanation ! thanks!
Thank you ❤️🙏😇
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 ❤️❤️
Why are we not using max-Heap(priority_queue) to store the max?
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
good explanation man!
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
Bhai contest k hard questions bhi krwa dia kro bhut buda solutions hote h aapke please
OP content
cfbr
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
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/
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 🙏
Thanks Bhaiya for amazing explaination #story_to_code
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.
Nice explanation
Thank you 😇🙏
thank you :)
You're welcome 😇🙏
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 😊👏
Thank you so much for watching 😇🙏
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 .
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 - ua-cam.com/play/PLpIkg8OmuX-KiAbBKuNidN-c66aHwBh3t.html
Candidates with >= 2 to 5 years experience - ua-cam.com/play/PLpIkg8OmuX-KrStViqRAIJV6MXej-tNy4.html
thanks so much bro.❤@@codestorywithMIK
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
class Solution {
public:
vector maxSlidingWindow(vector& v, int k) {
vector ans;
int i = 0, j = 0, n = v.size();
deque d;
while(i < k){
while(d.size() != 0 && v[d.back()] = d.front()) d.pop_front();
d.push_back(i);
i++;
}
ans.push_back(v[d.front()]);
while(i < n){
while(d.size() != 0 && v[d.back()] = d.front()) d.pop_front();
d.push_back(i);
ans.push_back(v[d.front()]);
i++;
}
return ans;
}
};
❤❤
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 ❤️😇🙏
Leetcode Contest mein hard question dekhkar lagta hai, nahi hoga, ye toh. Please make a video on it
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
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.
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?
Idx starts from 0.
Sir, time complexity pe ek video bana dijiye jisme nested loop hai but o(n) time complexity ho ,
Wo kaise ho raha hai samajh nahi a raha
Iska time complexity bhi nahi samajh aya
did this question before but forgot it
Everyone forgets. It’s alright.
Keep revisiting concepts. It will help a lot 😇🙏
//Bruteforce Approach
class Solution {
public int[] maxSlidingWindow(int[] arr, int k) {
int[] windowMaxima = new int[arr.length - k + 1];
for (int i = 0; i < (arr.length - k + 1); i++) {
int maxInWindow = Integer.MIN_VALUE;
for (int j = i; j < (i + k); j++) {
maxInWindow = Math.max(arr[j], maxInWindow);
}
windowMaxima[i] = maxInWindow;
}
return windowMaxima;
}
}
//Good Approach (Using Max Heap)
//Naive Implementation
class Solution {
public int[] maxSlidingWindow(int[] arr, int k) {
int[] windowMaxima = new int[arr.length - k + 1];
Queue maxInWindow = new PriorityQueue((a, b) -> b - a);
// Initialize the heap with the first window elements
for (int i = 0; i
16/31 #augustchallengewithMIK
Browser me dark mode use karo 😂
Sure 😇❤️