Sliding Window Maximum | Monotonic Deque | INTUITIVE | GOOGLE | Leetcode-239 | Dry Run
Vložit
- čas přidán 6. 09. 2024
- ****** 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.@@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
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 ❤️
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.
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 ❤️😇🙏🙏🙏
Your every explanation gives me a confidence that I can solve such type of questions… thank you sooo much 🙌
Best channel on CZcams for dsa
Hi Shivam.
It means a lot to me.
Thank you so so much ❤️😇🙏
💯
100% true
Superb and the only best solution I found for this problem. You have explained why duque is used. Thanks a lot
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 ❤️
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 😇😇🙏🙏
Thanks Bhaiya for amazing explaination #story_to_code
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🥲🥲😰
I solved this by using priority queue + hashing technique.
Wonderful 😇💪
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 your efforts for all of these videos are just next level
superb explanation
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
Please consider making videos on segment tree problems on leetcode.
❤️❤️ thanks for osm explanation
bhaiya yaar kya samjhaya aapne matlab gajab 🔥🔥🔥🔥🔥🔥
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
can you please upload the video solution of weekly contest of leetcode as well? it will be helpful a lot.
your way of explanation is awesome.🤠🤠
Thank you 😇❤️
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 Sir 🙏
OP content
cfbr
good explanation man!
great explanation ! thanks!
Thank you ❤️🙏😇
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 🙏
Amazing explanation
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 ❤️😇
🚨🚨🚨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
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 .
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
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! 😇❤️
Great Video 👌🏻
Thank you 😇
thank you :)
You're welcome 😇🙏
Awesome as always
Nice explanation
Thank you 😇🙏
u explained it so well❤
Thanks
Thank you 🙏 😇
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.
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
Sure noted. Let me plan a video on that ❤️❤️
Bhai contest k hard questions bhi krwa dia kro bhut buda solutions hote h aapke please
can we solve by storing number itself in deque not storing index .i tried this way but i get stucked to manage window size
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
❤❤
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
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/
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.
Thank you 😊👏
Thank you so much for watching 😇🙏
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 - czcams.com/play/PLpIkg8OmuX-KiAbBKuNidN-c66aHwBh3t.html
Candidates with >= 2 to 5 years experience - czcams.com/play/PLpIkg8OmuX-KrStViqRAIJV6MXej-tNy4.html
thanks so much bro.❤@@codestorywithMIK
why the window idx >= k-1 and not idx == k?
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 ❤️❤️❤️
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
16/31 #augustchallengewithMIK
did this question before but forgot it
Everyone forgets. It’s alright.
Keep revisiting concepts. It will help a lot 😇🙏
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
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.
Browser me dark mode use karo 😂
Sure 😇❤️