Sliding Window Maximum | Monotonic Deque | INTUITIVE | GOOGLE | Leetcode-239 | Dry Run

****** 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

[@herculean6748]

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

[@codestorywithMIK]

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 ❤

[@herculean6748]

@@codestorywithMIK now it is crystal clear, thanks!!

[@ankitshaw_3060]

Can you pin this comment...it will be really helpful for others also ...I had to find it after going through all the comments

[@codestorywithMIK]

@ankitshaw_3060 done ❤️❤️

[@ankitshaw_3060]

Thanks❤

[@GeniusOG]

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. ❤️

[@codestorywithMIK]

Hi @GeniusOG, This means everything to me. Thank you so much and I will never stop posting. Love and respect ❤️❤️❤️❤️

[@Momentsofmagic28]

hey how did you get that Rs. 40 tag in your comment ? Can you tell me, I also want to reward this legend

[@amitshukla2268]

click on three dots just right after like and share button and there you will find an option for thanks, use that.@@Momentsofmagic28

[@codestorywithMIK]

?????????? 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.

[@souravjoshi2293]

Thanks a lot

[@wearevacationuncoverers]

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

[@sauravfarkade7032]

Thanks Bhaiya for amazing explaination #story_to_code

[@kashishkashyap6229]

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; } }

[@codestorywithMIK]

🚨🚨🚨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

[@CodingJoySoul]

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"

[@wearevacationuncoverers]

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.

[@AlishaKhan-ww3io]

true

[@codestorywithMIK]

Means a lot ❤️

[@brokegod5871]

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

[@kamranwarsi12b22]

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]

Hi there, Can you please share Qn link ❤️

[@TheWorldBeyond007]

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 .

[@kishan.17]

superb explaination bro thanks so much bro for regularaly giving this beautiful content,🥰🥰🥰😍😍😘

[@codestorywithMIK]

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 ❤️😇🙏🙏🙏

[@Momentsofmagic28]

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.

[@Cityscapes411]

❤️❤️ thanks for osm explanation

[@wakeuppeggy]

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❤️

[@codestorywithMIK]

Much appreciated Shubham. Thank you so much for this ❤️❤️❤️

[@Momentsofmagic28]

me too

[@sachinmohanty4577]

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

[@codestorywithMIK]

Sure noted. Let me plan a video on that ❤️❤️

[@parthh1112]

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; } };

[@anuragv400]

good explanation man!

[@ugcwithaddi]

Your every explanation gives me a confidence that I can solve such type of questions… thank you sooo much 🙌

[@taneyasoni]

16/31 #augustchallengewithMIK

[@dayashankarlakhotia4943]

this is one of my favorite problem good explanation. i was struggling so much dequeue approach past now i understood very well

[@codestorywithMIK]

Thank you so much. My favourite too

[@saurabhtiwari9614]

I solved this by using priority queue + hashing technique.

[@codestorywithMIK]

Wonderful 😇💪

[@ManasNandMohan]

OP content cfbr

[@chaitanya812]

CAN U RECOMMENED SOME MORE DECREASING DEQUE CUZ MOST OF THE TIME ITS INCREASINGN

[@codestorywithMIK]

Some qns based on Monotonic Decreasing - leetcode.com/problems/daily-temperatures/ leetcode.com/problems/132-pattern/

[@Tejaswi-xd4re]

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..

[@codestorywithMIK]

Sure thing Tejaswi How about I make a video this Weekend on that ?

[@3011hi]

@@codestorywithMIK yes sir pls make that video

[@Tejaswi-xd4re]

@@codestorywithMIK yes sir pls make it ASAP.. It will be very helpful

[@aditigupta6870]

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.

[@xiaoshen194]

Ek specific video bna denge chota Sa jisme aap recur+memo ko bottom up mein convert krna sikha dein 🙏

[@codestorywithMIK]

I will surely cover that in my "DP Concepts & Qns" Playlist

[@codestorywithMIK]

Also, since today, this is a very important video, I would love to know if it was explained well. Thank you 🙏

[@xiaoshen194]

@@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.

[@xiaoshen194]

​@@codestorywithMIKbeautifully explained sir. Let me see if I am able to solve the description wala ques now. Thnx ❤❤

[@ajubgamer5350]

Bhaiya kya app iPad ke notes upload kar sakate ho revision ke lie

[@codestorywithMIK]

Started attaching from today onwards. Today’s Leetcode POTD will have PDF Link attached in the Description of the video

[@ankit80354]

can we solve by storing number itself in deque not storing index .i tried this way but i get stucked to manage window size

[@dayashankarlakhotia4943]

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

[@souravjoshi2293]

I wish I could like this video a million times.

[@prakhargarg4166]

Leetcode Contest mein hard question dekhkar lagta hai, nahi hoga, ye toh. Please make a video on it

[@nikhil4062]

why deque is used instead of queue?pls explain

[@codestorywithMIK]

?????????? 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.

[@AryanMishra-yh4ic]

can you please upload the video solution of weekly contest of leetcode as well? it will be helpful a lot.

[@AmarjeetKumar-to9ub]

thank you :)

[@codestorywithMIK]

You're welcome 😇🙏

[@nikhilsatyam4815]

bhaiya your efforts for all of these videos are just next level

[@RahulGuptaa29]

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

[@codestorywithMIK]

Thank you so much for java ❤❤❤

[@Momentsofmagic28]

Thanks a lot for java bro

[@shreytolasaria2633]

did this question before but forgot it

[@codestorywithMIK]

Everyone forgets. It’s alright. Keep revisiting concepts. It will help a lot 😇🙏

[@AlishaKhan-ww3io]

Superb and the only best solution I found for this problem. You have explained why duque is used. Thanks a lot

[@HoppyGamer]

Please consider making videos on segment tree problems on leetcode.

[@ishwarkoki1119]

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

[@codestorywithMIK]

Thanks a lot 😇🙏

[@wearevacationuncoverers]

thanks for python

[@DR-mq1le]

great explanation ! thanks!

[@codestorywithMIK]

Thank you ❤️🙏😇

[@Ramneet04]

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

[@ManojKrVerma-vw4dx]

humne peeche se hi kyun delete kiya... i think aage se bhi delete krne se accept hona chahiye ?

[@codestorywithMIK]

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.

[@ManojKrVerma-vw4dx]

thanks it makes sense it is now clear to me.@@codestorywithMIK

[@study-yd6es]

Amazing explaination !!

[@UtkarshPatel-v9o]

superb explanation

[@kartikrameshchavan6662]

Thanks Sir 🙏

[@easyvedicmaths886]

why the window idx >= k-1 and not idx == k?

[@codewithsk5471]

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.

[@codestorywithMIK]

Sure noted ❤️😇

[@39_jatinjain4]

your way of explanation is awesome.🤠🤠

[@codestorywithMIK]

Thank you 😇❤️

[@sachinmohanty4577]

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 😢

[@codestorywithMIK]

Let me share an excel sheet soon and you guys can fill in the problems there ok

[@kunal4710]

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

[@codestorywithMIK]

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

[@aaravmishra3487]

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

[@codestorywithMIK]

Awesome ❤️❤️❤️

[@kashishkashyap6229]

Was waiting for this!

[@codestorywithMIK]

Means a lot. Since today is a very important video, I would love to know if it was explained well. Thank you 🙏

[@kashishkashyap6229]

​@@codestorywithMIK I completely understood the story. Thanks a lot ! You never disappoint.

[@codestorywithMIK]

Thank you 😇😇🙏🙏

[@nikhilsatyam4815]

bhaiya yaar kya samjhaya aapne matlab gajab 🔥🔥🔥🔥🔥🔥

[@dianayao1677]

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

[@shivamjadon2257]

Best channel on KZbin for dsa

[@codestorywithMIK]

Hi Shivam. It means a lot to me. Thank you so so much ❤️😇🙏

[@Momentsofmagic28]

💯

[@wearevacationuncoverers]

100% true

[@tutuimam3381]

Amazing explanation

[@pratyushpandey1145]

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

[@codestorywithMIK]

Sure thing. Means a lot to me Pratyush for trusting my small channel. ❤️❤️😇

[@pratyushpandey1145]

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🥲🥲😰

[@Kumar-up2lj]

Bhai contest k hard questions bhi krwa dia kro bhut buda solutions hote h aapke please

[@himanshigoel7510]

Sir i solved it using set, is it fine?? vector maxSlidingWindow(vector& nums, int k) { sets; for(int i=0; i

[@wearevacationuncoverers]

Wow. this is good bro.

[@kishan.17]

bro and pls make a video on hoe system design in important or interviews and hot to start and some tips on system design .

[@codestorywithMIK]

For Freshers and 1-2 years of experience - kzbin.info/aero/PLpIkg8OmuX-KiAbBKuNidN-c66aHwBh3t Candidates with >= 2 to 5 years experience - kzbin.info/aero/PLpIkg8OmuX-KrStViqRAIJV6MXej-tNy4

[@kishan.17]

thanks so much bro.❤@@codestorywithMIK

[@humanity7880]

Thank you sir! Awesome explanation

[@codestorywithMIK]

Most welcome! 😇❤️

[@shabananoor9423]

Awesome as always

[@anuppatankar4294]

Great Video 👌🏻

[@codestorywithMIK]

Thank you 😇

[@souravjoshi2293]

Finally it's here

[@codestorywithMIK]

Means a lot. Since today is a very important video, I would love to know if it was explained well. Thank you 🙏

[@oqant0424]

u explained it so well❤ Thanks

[@codestorywithMIK]

Thank you 🙏 😇

[@girikgarg8]

Nice explanation

[@codestorywithMIK]

Thank you 😇🙏

[@codeandtalk6]

❤❤

[@codestorywithMIK]

Means a lot. Since today is a very important video, I would love to know if it was explained well. Thank you 🙏

[@codeandtalk6]

Best explanation bro. I haven't understood why people are using dequeue but you made it very clear thank you ❤

[@codestorywithMIK]

Means a lot. Thank you so much. I will make another video soon on why priority queue can also be used to solve this ❤️😇🙏

[@MounikaEMB]

Thank you 😊👏

[@codestorywithMIK]

Thank you so much for watching 😇🙏

[@yadav.nitin03]

Browser me dark mode use karo 😂

[@codestorywithMIK]

Sure 😇❤️