so let's continue with our stack and Q playlist for starting off he welcome back to the channel I hope you guys are doing extremely well so the problem that we will be solving today is sliding window maximum so what is the problem statement stating that you'll be given an ums aray you will be given a value of K now your task is to start with the first window of the size K so over here you start with the first window of size K and you get the maximum out of it so what will be the maximum that will be three of the first window of size K perfect if I ask you what is the next window now this was the window which one is the next window can I say if I slide it by one place this will be the next window which is typically this one and what is the maximum unit again three so you write a three so I can say that in this particular window the maximum is three again you go to the next window so if I have to go to the next window can I say that this is my next window so I'll end up just erasing this I'll have the new window as this one what is the maximum can I say five I again and if I ask you what is the next window I can just slide it and this will be my next window so I'm at my new window now what is the maximum five again I slide it this time this will be my new window can I see this yes I can so I can erase it what is the maximum again five again make sure you move to the next window which is this one so if I move to the next window what is the maximum the maximum is three again I can say move to the next window which is this one so I can just erase the current window and move to the next and the maximum is six after that I don't have any other window and if I don't have any other window me stop so if you try out all the windows of three you will get a maximum of from each of these windows you store them in a list or an array and that is what you will be returning so what is the na solution to this one I know one thing for sure we start from index zero and we could straight away scan the next K elements after that we move to the next index and again scan the next you know three elements or k elements and again move to the next and again scan three again move to the next and again scan three again move to the next and scan three and so on I can go on till here because this is where I'll get the last three elements if I have to write down the indexes it's 0 1 2 3 4 5 6 7 8 till sixth index is where I'll go for n equal to 9 so that's 9 - 3 9 - K is where I'll go to okay I know that for short so what I'll do is I'll keep keep a list where I'll store all the answer and I'll start by saying okay I can Traverse from I equal to 0 till n minus K because that is where till I can generate all the windows I can store a maximum and I can say that the maximum initially will be array of I I know the elements will be from I equal to how many if I say this is 0o this is 1 2 so I take till K Elements which is nothing but 0 + 3 - 1 which is nothing but I + Kus 1 can I say this I can because if I is here I + K - one so I'll go to I + K minus one perfect and it'll be very simple Maxi equal to Max of Maxi comma array of J that will give me the maximum of that particular window once I have it you could do a list. add or whatever language you're using you could just push the Maxi to it and once you're done you could end up returning the list and that's it so what will be the time complexity I can say that this is running for B go of n minus k for sure I can say that this is running for beo of K so the overall time complexity will be n minus K multiplied with k for sure B of n minus K multiplied with B of K what about the space complexity I'm running it for n - K because till n minus K because I have n minus K windows so I can say the number of windows will be equal to the number of maximum size tool that'll be the size of the list so n minus K is the size of the list perfect so this is where the interview will not be happy because you're running a nested Loop kind of a you know algorithm they'll ask you to optimize this so we need to optimize our Brute Force solution and The Brute Force what I was doing was I was scanning through each and every window and that is the reason I ended up taking quadratic time complexity and the interviewer is asking you to optimize a somewhere near about B of end time complexity that means it's an indication that you should start looking at a beo of end time complexity which means I'll have to solve it while doing a single traversal while doing a single traversal can I do it what was I doing previously I was going through each and every window and then I was scanning through it to get the maximum what if I say that hey maybe I can just Travers maybe I could just Travers and keep a track of K elements how will I do that it's simple yes yes yes yes but when you add minus three you are having four elements with you so you just trim it off after that when you have five you trim after that when you have three you trim after that when you have seven you you trim after that when you have one you trim so every moment you're keeping a track of K elements so the first priority is you know tracking like keep a track of key elements like keep like just keep the window elements don't keep anything outside keep the window elements that's the track keep the window elements perfect so which means whenever I'm at seven I'll add it I'll add it and at the same time I'll delete it so I need a data structure which adds and you know throws out the outside perfect what else I need imagine I'm at this particular place which is 537 and I need the maximum in order to get the maximum I'll have to scan through each and every element in that window and that is what was taking time so I cannot scan through I cannot scan through this is where I'll use the concept of monotonic stack I'll explain you it's very simple and I'll be like I'll be storing elements in a decreasing order why decreasing order as I go through in the dryon you'll start understanding why decreasing order how did I end up understanding that it is a monotonic stack you have to do you know a bit of here and there you'll have to do play around with pen and people then it will start coming to your brain it will take time but if you have the knowledge of monotonic Stack you should Implement whenever you need the greatest or you need the smallest you know in constant complexity whenever you need greatest or smallest in constant you should think of monotonic St got it okay so I know one thing I need to keep the window elements that means I need to add and I need to delete I need to add from the front I need to delete and in order for monotoring stack I need just a stack I need a data structure stack I need a data structure which kind of you know adds and deletes I need a two-way data structure like something which is you know open from both the ends so that I can I can add and I can delete okay so do I use a stack and a data structure for K elements no I use a single data structure and that is nothing but the W DQ my bad maybe I can write something like this so this is the DQ data structure so what this allows is this allows you to you know push from the back this allows you to pop from the back and this is what acts as your stack you could always push back that is similar to you know stack dot push and you can pop back that is pretty much similar to pop in stack okay and what you could do is you could also push front you could also push front and you could also pop front white simple now this is what will be required to take out elements because you'll be taking out elements every time you move so this is a data structure where the Right End can be used as a stack and the left hand left side could be used to know remove elements so what I've done is I've drawn the DQ yes but I've kept it open so that you know that from the top we insert stack elements and from the bottom you could always remove elements so this is a DQ which is going to store index and values not values values is just for your reference so what I will be doing is I'll be starting with the first element right and that is one index zero and the DQ doesn't have anything so you could simply just push back in this stack so it'll be like zero the next with a value of one value is just for reference I'll be moving to this one so when you are at the index one first thing you have to keep in mind is is are you storing anything outside window remember the window is something here so it's still not storing like you storing zero index it is still not outside your window of size three say okay but you have a three you have a three and as I told you we will be maintaining a monotonic stack which is decreasing in nature so I have a three now tell me one thing if you have a three is there a point because I'm looking for maximum is there a point of storing one no there's no point of storing one because if you have a three this literally no point of storing one this is where you'll say that Hey listen can you just you know go out okay he's gone so I'll be storing index one and a value three perfect after that I'll be coming to minus one so when I come to you know minus one I'll be like this is my window this is my window so look at the stack stack is having element one right that's the last element that we have and that is okay that is inside the window because the window ends at zero that is inside the window so the window we are still carrying the you know correct window what is the next thing we have a minus one now you might say that hey we have a three why will we store minus one I'll tell you why imagine this isus 5 and when the window is this much tell me which is the maximum - 5 is not Max maximum minus one is maximum so you'll have to store minus one because when three is gone when three is gone you need the next you need the next greatest element got it that's why I'm storing like this 3 minus one so when three is gone still have minus so what you'll do is you'll take that minus one which is at index two and you'll put it in so we are storing in a monotonic decreasing fashion if you see which is like this no not like this like this monotonic decreasing fashion perfect what is the next so before going next you are at your first window size so can you get me the maximum yes because I'm storing in an increasing fashion you could straight away get the element from the back you know from the front in DQ this is front inq this is front so you could straight away get from the front so I'll get the element and that is three so I can straight away write the element three after that I'll move here so when I move here again I'm at three I know the window is still one is it valid yeah the last element is still valid so I can keep it so I have a minus three can I put it into the stack yes I can because even if I put it it still maintains a decreasing order and the index is three if I want because I want the maximum because this is new window I want the maximum for it so again you look at the front element and that's three so you could just pick it up next you go to four so when you go to the fourth index you know this this is where you are this is where you are correct till second is what you can allow so at Max one element will go up from the stack which is the last element so you could go and do a pop front you could go and do a pop front so this will go you could easily take it out right that's why you need a dou ended Q perfect so I've taken it out so I'm maintaining the the window now what is the next thing I need the greatest tell me if you have five if you have five do you actually need minus three do you actually need minus one no that's where you end up first deleting this then deleting this and eventually entering the fifth element which is at index 4 so now you are again at a window and if I ask you what is the maximum you look at the front element which is five so you see that five is my and then you go across here so when you go across here first thing is maintain the key elements so you'll be like okay which is the last three and this is still four it is inside my window what's the next you got three so you could straight away say that okay I can just keep the lower element and I can write the index as five perfect and if I ask you for this window which one is the maximum you'll again look at and you'll see that five is the maximum so you'll take five after that you'll move across now this is where you get seven so when you get seven you're like Hey listen I don't need three I don't need five but before that please make sure this is where you are this is where you are okay and this is the last in index of the window and this is still valid you don't have to remove now you're looking for seven seven is very big so what you'll do is you take this out here'll take this out everyone is gone I take the window six and the value seven and for this window the answer will be seven after that we coming across to one so you could just keep on doing this process very simple very very simple so what I'll do now is I'll write down the pseudo code so you have to write down the function and the the function will be having an array and a value K what do I need to return I need to return a list right so I can define a list and what will be that like what will be the size of the list can I say this number of you know number of maximums of windows will be n minus we already did it these many windows we'll have so you can define a list of that size perfect now what you can do is you can also Define a DQ I'll start traversing from I equal to 0 till nus1 what the first thing you'll do we'll check hey if there's someone who is not in my window so let's go back imagine you're standing at 5 and you know the window is valid till three which is typically 5 minus K which is three that gives you two so if anyone is equal to two or anything under two anything equal to or under two so you'll be taking it out so you'll be like Hey listen I know at Max there can be one element because when you're adding one you'll always remove one from the back you'll be like Hey listen if the DQ is not empty please always check it please always check it if the DQ is not empty and and the DQ do back is lesser than equal to very important the current index minus K that's the case hey you can't stay by the way DQ do front not back DQ front not back you could say that DQ do po front perfect so it be just taking it out so made sure that it is maintaining the correct window elements what is the next job to make sure that we maintain greater elements so be like okay I need to maintain greater elements so maybe I could do a while stack. Mt not stack DQ Mt and and we playing with stack like we're playing with DQ which is treated as stack so it'll be like hey array of DQ dot back if that value you know is lesser than but you can say lesser than equal to because there's no point in storing the same elements as well array of I do I need to store it no this is when you say DQ do pop back so you throw out you end up throwing out everything and once you have throw like thrown out everything you basically end up saying DQ do push because this is where you push I very important you push I not the element and after this where does your first window start remember the first window starts at K minus one so if your window has started which means if I is greater than equal to K minus one then your list will have an answer to add and what will be that answer that answer will be array of DQ dot front because the stack is maintaining a monotonic order the last element so the last element is front and that will be your answer perfect and I could say that the follow Loop is over and eventually I could end up returning the list and the function is over so now it's time to analyze the time complexity can I say this that this is definitely taking a b go of N and then what I'm doing is I'm popping out I'm taking it out I'm pushing elements so at Max at Max I'll end up pushing n elements so at Max even if I'm popping it out it'll be n times so even if the while loop if I combine everything because what they're doing is you know taking elements out if I pushed n elements if I pushed n elements the maximum they can take out as n elements thereby this will be B go of n overall as nothing else so what I can say is the time complexity is B go of 2 N because n for traversal and n Pop backs n put pulling out elements what about the space complexity at any moment in the DQ I'm not storing more than K elements I'm just storing the window size elements plus I need the answer so that's a n minus k n minus k for the list because they storing the answer as well this will be the overall time complexity and the space complexity for this particular solution I hope youve understood it so if you're still now watching and if you've understood everything please please do consider giving us a like and if you're new to our channel do consider subscribing to us as well with this I'll be wrapping up this video let's me some other video why careen don't forget your golden I will find