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

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

[@thekindspill]

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

[@bhagirathmakwana9112]

​@@thekindspill Use thanks option of video

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

[@thekindspill]

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.

[@omkarsawant9267]

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.

[@codestorywithMIK]

👍🏻♥️

[@souravjoshi2293]

I wish I could like this video a million times.

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

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

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

[@shivamjadon2257]

Best channel on KZbin for dsa

[@codestorywithMIK]

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

[@thekindspill]

💯

[@wearevacationuncoverers]

100% true

[@ugcwithaddi]

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

[@AlishaKhan-ww3io]

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

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

[@thekindspill]

me too

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

[@nikhilsatyam4815]

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

[@nikhilsatyam4815]

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

[@UtkarshPatel-v9o]

superb explanation

[@39_jatinjain4]

your way of explanation is awesome.🤠🤠

[@codestorywithMIK]

Thank you 😇❤️

[@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 😇😇🙏🙏

[@Anujrajesh-r5b]

very nice explaination sir

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

[@Cityscapes411]

❤️❤️ thanks for osm explanation

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

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

[@tutuimam3381]

Amazing explanation

[@HoppyGamer]

Please consider making videos on segment tree problems on leetcode.

[@sauravfarkade1928]

Thanks Bhaiya for amazing explaination #story_to_code

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

[@DR-mq1le]

great explanation ! thanks!

[@codestorywithMIK]

Thank you ❤️🙏😇

[@kartikrameshchavan6662]

Thanks Sir 🙏

[@AryanMishra-yh4ic]

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

[@saurabhtiwari9614]

I solved this by using priority queue + hashing technique.

[@codestorywithMIK]

Wonderful 😇💪

[@anuppatankar4294]

Great Video 👌🏻

[@codestorywithMIK]

Thank you 😇

[@humanity7880]

Thank you sir! Awesome explanation

[@codestorywithMIK]

Most welcome! 😇❤️

[@shabananoor9423]

Awesome as always

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

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

[@oqant0424]

u explained it so well❤ Thanks

[@codestorywithMIK]

Thank you 🙏 😇

[@study-yd6es]

Amazing explaination !!

[@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 ❤️😇

[@Kumar-up2lj]

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

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

[@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 🙏

[@anuragv400]

good explanation man!

[@ManasNandMohan]

OP content cfbr

[@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 ❤❤

[@girikgarg8]

Nice explanation

[@codestorywithMIK]

Thank you 😇🙏

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

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

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

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

[@AmarjeetKumar-to9ub]

thank you :)

[@codestorywithMIK]

You're welcome 😇🙏

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

[@prakhargarg4166]

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

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

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

[@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/

[@MounikaEMB]

Thank you 😊👏

[@codestorywithMIK]

Thank you so much for watching 😇🙏

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

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

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

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

[@easyvedicmaths886]

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

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

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

[@shreytolasaria2633]

did this question before but forgot it

[@codestorywithMIK]

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

[@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 ❤❤❤

[@thekindspill]

Thanks a lot for java bro

[@taneyasoni]

16/31 #augustchallengewithMIK

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

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

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

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

[@yadav.nitin03]

Browser me dark mode use karo 😂

[@codestorywithMIK]

Sure 😇❤️