So with this video we will be starting off with the two pointer and the sliding window playlist from the strivers a to z ds echoes in case you haven't checked out our ds echoes please make sure you check it out the link will be in the description but before starting off hey everyone welcome back to the channel i hope you guys are doing extremely well so this video will be an introductory video for the two pointer and the sliding window playlist so one thing this is not a typical algorithm that you'll have to uh you know memorize This is more like a constructive algorithm where you need to understand the concept and then depending on the problem statement you'll have to mold that concept and solve that problem. So in this video I'll be talking about four different pattern of problems that you can see when it comes to 2.0 and sliding window in interviews and I'll also be giving you some templates which will help you to solve most of the problems in this particular playlist. And after this video we'll be solving a bunch of problems on 2.0 and sliding window like But please, please make sure that you watch this video till the end because you'll understand the patterns and specifically the template that we are going to reuse in most of the videos across this particular playlist.
So we generally see four kind of patterns in this particular topic. The first one is where it's a constant window. So let me give you an example. Imagine I give you an array, okay? So this array can have positive as well as negative numbers.
I don't care. Imagine this is the array. And imagine I give you k as 4. And I give you a very simple problem.
Hey, given an array with positive and negative integers, given an integer k, your task is to figure out the maximum sum that you can opt... by picking up four elements consecutively. Let me explain. If I pick up these four elements consecutively, the summation that I'll get is 3 plus 3, 6 plus 2, 8, 8 minus 1, 7, right? So, I have to pick up four elements consecutively.
You can pick up this one as well. What you cannot do is pick up two from here, two from here. That's not allowed consecutively.
So, The question is already stating the size is constant 4. So I'll have to use this into picture. For an example, what I can do is I can straight away say, okay, I know one thing. This is 0th index, 1st index, 2nd index, 3rd index, which is typically k minus 1th index. So if it's a problem of constant window, what we generally do is we take two pointers, take an L, take an R, right? First.
compute the sum so you can run a loop from l to r that's going to be super simple from 0 to k minus 1 right where you can say that initially l is at the 0th index r is at the k minus 1th index you can run a loop from l to r and the summation that you will get is minus 1 plus 2 plus 3 plus 3 that is 7 3 plus 3 6 plus 2 8 yeah 7 so you got a sum of 7 and that is typically for this particular window right this is a consecutive four elements what is the next window the next window is going to be this one right so the constant window shifts what is what has happened for the next window for the next window if i use a different color or maybe i can just use the same color the first window was this one what has happened for the next window nothing but this is the next window right what has happened tell me tell me tell me tell me you trim off you take off the last element and you add up one more element so you Can I do that? It's going to be super simple. You move r to one place ahead, you move l to one place ahead.
But the condition is, before moving l, you'll have to take out this minus 1 from the sum. So you can keep on doing this. And you know that the last window will be when r reaches over here, the last window will be this one. So you keep on going till r is not crossing the boundary.
It's going to be super simple. While you can straight away do r, can go on till the size, right? So whenever it is constant, first thing you'll have to do is move the l for the next window. But if we're doing that, you can say sum equal to sum minus array of l, right? And the other thing that you can do is l plus plus.
And that goes with l. Now what about r? Sum equal to, first you have to do r plus plus. then sum plus array of r simple that is what you do and you know you can only move r when r is here and then it can move here when r is here it cannot move beyond it so only thing that you'll have to change is the condition gets altered that's it and you get the sum so what happened is now you have the orange you have the orange windows sum and you can easily compare it with some max sum equal to max of max, sum, comma, sum and done.
That's it. Initially the sum can easily be figured out by running a loop from L to R. How tough is that? You can keep a max sum variable.
So this is how the constant window problems will work. You'll have to first assign the constant window depending on the condition. Over here the condition is pretty simple. Depending on the conditions, you'll have to do your job.
You can run a for loop and do your job. And after that If it's a constant window, you move it. So you decide how to move it. Just make sure you keep this condition in check.
Because you're doing an R++, if you keep R lesser than N, that will be out of boundary. So that's the first one. Not, it will not be asked a lot of times. We'll be doing one problem on this one because I haven't seen it that much in interviews.
But still, it's just good to know. The second type of pattern will be. You'll be given something like longest subarray or a substring.
Yeah, longest subarray or a substring, depending if it's an array problem or it's a string problem, where and then there will be a condition. This is the most common type of problem that you will see across this playlist or across this topic on the internet. And most of the interview problems are on this particular pattern.
So please listen to this carefully. Let's take an example. Longest subarray matches the pattern. Longest subarray can be a substring if it is a string problem.
We'll be doing that across the playlist and then there is a my bad and then there is a condition. This is the condition. You know what is a subarray? Any consecutive portion of the array.
Any consecutive portion of the array right? Maybe I can pick up this and this can be called a subarray whereas 1 and 10 cannot be called a subarray because it is not consecutive. A single element is also subarray.
The entire array is also a subarray. Remember this, okay? You'll have to pick up the longest subarray where the sum is lesser than equal to k, where k is given to you. So, maybe if I pick up this one, what is the sum? Sum is 7 plus 7, 15. 7 plus 7, 14 plus 1, 15. Whereas this is not.
lesser than the sum. So this subarray cannot be picked. Can I pick up the subarray? Probably yes, 7 plus 1 is 8 plus 5 is 13. And this is lesser than this one. Do you find any other subarray?
I typically don't find it. Like I'm not able to find any other subarray. This is the longest subarray where the sum is lesser than equal to k.
So you'll have to return in questions, they might ask you to return the subarray. In question, they might ask you to just return the length of the subarray. It will depend on the question.
So in these questions, there is typically a three format way to follow. The first one is you start off with the brute force, right? Then you go to the better solution and then you optimize it with the optimal one. Okay.
And there's a very straightforward template to it. So when I'm talking about a brute force, it's What will be a brute force for this one? Think of it.
Generate all the subarrays? Yes. So a typical brute force will be to generate all the subarrays and that's going to be the template.
You'll always generate all the subarrays and check with the condition. Now when I'm saying generate all the subarrays, what do I mean by that? You know how to generate all the subarrays if you have seen my arrays playlist.
It's going to be very simple. You stand at an individual element and you generate all the sub arrays that is possible with that element and i know single element is possible you attach five you attach one you attach seven you attach ten all the sub arrays with two done then you move to the next you generate all generate all generate all then you move to one generate generate generate then you move to seven generate generate then you move to ten and that is the only one so you have to generate all the sub arrays how you can do is so Because we are going through each and every element what you can do is you can start from zero and you can go on till n minus 1 at index because every element is considered as the first element of a subarray. After that what's happening?
When i is here, you start with this element, then the j goes here so you take one more, then the j goes here so you take one more, then the j goes here so you take one more, then the j goes here so you take one more. So there's a j that starts with the current element. So what you can do is, you can simply take a j which starts from i and goes till n minus 1. That's it. and you're able to generate all the sub arrays.
That is how you'll generate all the sub arrays. Now this particular problem was saying sum, right? So depending on the conditions, now you'll be writing the other things, but this will be a typical template to generate all the sub arrays.
Now what is the question asking? Sum in the maximum length. So maybe I can keep a max length equal to zero initially, right? So can I say If I'm looking, if I'm standing here, this is the initial subarray and the sum is 2. Then you attach 5, the sum is 7. Then you attach 1, the sum is 8. Then you attach 7, the sum is 15. Then you attach 10, the sum is 25. Keeps on increasing.
So maybe what I can do is, I can keep a sum equal to 0. And then I can write, hey, if sum is lesser than equal to k, that's my condition. That is my condition, isn't it? But before doing this, you will have to add up this element.
Please add up this element, done. And if it is, you can straight away update max length equal to max of max length comma, what is the length of the particular subarray? If i is standing here and the j is standing here, that means all the four elements are here and the length is j minus i plus one, based on the mathematics.
So what you'll do is j minus i plus one, done. And that will be it. And eventually you can straight away print your max length. Now, there might be optimizations across and optimizations are very simple.
You'll have to think about it. Now, over here, I can think of an optimization. I'm looking for some lesser than equal to 14. So I know one thing.
I'm adding 2, 5, 1, 7. At this moment, what happens is 2 plus 5 is 7 plus 8, 15. The sum is 15. Do I need to go and add? 10. There's no point. So these optimizations you have to think of. Something like I can put an optimization else if sum exceeds k, I can break off. I can put an optimization.
I'll break off. This is what you will have to think of. So this is how the brute force can be written.
And if I have to analyze the time complexity, it will be big of n square, near about, because two loops are running. And what about the space complexity over here? It will be big of 1. So the pattern will be same across every problem.
You will have to deal with the brute force at first and that will be generating all the subarrays and the template will be this one. Condition goes over here and if there is an optimization, you break out and depending on the condition, you can think of it, right? So this will be the brute force for the pattern number 2. Now let's quickly discuss the better one as well. So the better approach will be to implement the two pointer and the sliding window in such cases.
So what you will typically do is like this is the standard behavior across all the problems. We'll start with a window size of one. Okay, so I'll take a sliding window size of one. So I'm talking about a sliding window. So that typically means a window, right?
So the window will always have two pointers left and right. The left signifies the leftmost portion of the window. and the right signifies the rightmost portion of the window. So if I'm talking about one window size, you typically start with L and R. And since this particular problem is saying sum, what you'll do is you'll take initially the sum to be zero.
After this, there are two concepts of window. One is expand, one is shrink. Usually expansion happens for the variable R, which is the right edge of the window and the shrinking happens for the left edge of the window remember this in your brain okay so this is the current window so always when you start off whatever is your condition over here it is sum so add it to your sum 2 because the you're looking for a sum so current window should go into your sum done so what i'm saying is this window is having a sum of 2 is that lesser than equal to k because that is the condition and i'm saying yes So that is the case what you can do is you can update the max length and what is the max length one because that is the windows length as of now.
one length window. So what am I looking for? I'm looking for longest.
So generally what you will do, you'll try to expand, you'll try to increase the window size. So in such cases, what you'll do is you'll try to increase the window size. Standard, you take the R to the next one and if you take it, the summation increases to 7. Does this window satisfy the condition? You say yes, yes it does and if it does, you update the max length to 2. Perfect. Again you can go ahead and do the next thing.
You can again opt for widening the window. So this time this is the window that you're looking for and the sum will be updated to 8. Is this a valid window? This is because the summation is still less than equal to k.
So the length can be updated. At any moment the length of the window is r minus l plus 1. Simple maths. Keep it in your brain. Done.
What is your next job? Now this is where you start understanding. The next job moves to r and 8 plus 7. gets to be 15. So when the window, when the window has a sum that's greater than the given condition, like it's greater than k, which is a false condition, which is a false condition. Whenever a false condition happens, you try to shrink, you try to shrink and come for like, come inside that condition, come inside that condition because now the window is violating the condition. You don't want to violate.
So what you try to do is because you're moving. window is moving in this direction, expanding. You try to take out elements from the left. You try to take out elements from the left till you get the condition to be valid again. So what you will do is always shrink from the left, shrink 2, you take out 2. So the moment you take out 2, the 15 boils down to be 13. And this time, the R moves ahead and you say, okay, this is the window and sum is 13. Is this valid?
you say it's valid and you can take this window you can take this window and the window can be updated but you already have a length 3 so no need to update so you have to shrink the window but over here you shrink by one place you shrink just by one place in certain conditions it might happen for an example i can give you a very very simple example over here i'll just go back some steps okay okay so i've gone back to this step and imagine just imagine this is not 7 and this is uh something like a 10 yeah that's a better one something like a 10. Now what happens is when you take r and you move it here you add 10 which is typically uh adding like 18 you're typically adding 18 to the answer right. So what you're seeing is this particular window size has a sum of 18 which is again violating the condition so you have to shrink the window. So when you're shrinking You take off 1 which is 2. So when you take up 2, it gets down to 16. And the L goes ahead.
Now this is the one you need to understand. You have a 16 and this is the window. Not a valid one. Still violating the condition. So you re-shrink it.
You re-shrink it and you take out 5. Now it is a valid one. Now this is a valid one. So you can again compare the length. The length is 2. and you don't need to update the max length so you continue with your job which is moving the r so again when you move out this becomes 21 which is not a valid so you'll again shrink so i got this concept got this concept so i have to write down the code it's going to be super simple what i'll write is let's again analyze what we did uh i'll quickly erase this in order to understand how the template works so what did we do we typically uh Started with the L equal to 0, started with R equal to 0, started with the sum equal to 0, started with the max length equal to 0. Over here, only this portion will be variable, everything else will be constant in the template. Remember this.
And after that, what you can do is you can write while R lesser than N because that is how much you can expand the window. Okay. And what's the first step?
Sum equal to sum plus Array of n, array of r, because that's the new element that you're adding to your window. Okay, after this, we were saying that if it's a valid window, if it's a valid window, how do you know it's a valid window? Very simple. You say sum is less than equal to k. This is a validity check.
And in that scenario, what you did was max length, max of max length, comma r minus l plus one. That's it. But what if it was not valid?
What if it was not valid? You made it a valid window if you remember. If you remember? When it appeared like this window was invalid.
So you took off this, you took off this and you made it to be a valid window. You shrinked it so that it's a valid window. And then you checked for the length.
So before this, before this, you'll have to check. You'll have to check for the validity. If it is not, you'll have to shrink.
You'll have to shrink. So maybe I can have a check. You can either write if, but I'll try to combine the shrink and the check condition together. What I'll say is, okay, what is the case?
If sum is greater than k, I know this is an invalid condition. This is an invalid condition. In such a scenario, I will be taking sum equal to sum minus area of l. I'll take out l and I'll move l equal to l plus 1, isn't it? And I'll keep on doing, keep on shrinking it till it is.
So what I did was, I did put a conditional check. At the same time, I did put a while. So that is. keeps shrinking it till it's a valid one and when it is valid it will automatically update the max length. There's one more thing you'll have to do is you have to do r equal to r plus one. After this you have to go to the next element.
So this is pretty much it and at the end of the day you can go ahead and print the max length and if you are asked to print the subarray this is where you'll have to store the l and r. Store lndr if you are asked to print the subarray because this is where the max length is getting updated You have to store the lndr in case they are asking you for the subarray. Remember?
So what will stay constant throughout? Firstly lndr is going to be constant in the template remember this max length typically in all longest you will have to have it. This stays constant.
Again this one is a condition based depending on the condition depending on the condition the while loop will always stay constant because it is the shrinking stuff only this one will go to the condition right and this is again condition driven whereas the shrinking stays constant the expansion stays constant and the max length update stays constant you'll see this pattern being followed everywhere everywhere remember this and over here we'll discuss the time complexity What is the time complexity? So you might think, you might think that there's one while loop, there's another while loop. So it's a B go of n square, but it is not. Because if you look forward, L and R was here and then R kept on moving, R kept on moving, R kept on moving.
It's R, this R will at max move from here till here. That's a B go of n. At max, R will move for B go of n, not more than that.
Got that into your head? But. what about L?
So I'm moving L, I'm taking it off. I'm moving L, I'm taking it off. So at max, you'll take off how many elements?
N elements at the worst possible case, not beyond it, not beyond it. But will you do it always? No. In some steps, this shrink will work in some steps. So overall, sometimes you might take two, then you might take one.
then you might take one more overall you might end up taking all the elements overall overall so can i say overall r will work for b go often and the shrinking will work for b go often so overall it is b go off to n and what about the space complexity again over here it is b go of 1 but depending on the problem statement if you're using a map data structure depending on the condition we'll see in the later problems so this will be the time complexity which is b go of 2n. Now this is going to be the better solution. I'll have to optimize this. Now if you're looking at a b go of 2n, how much further can I optimize?
If the array is having 2n elements, sorry if the array is having n elements, how much can I optimize 2n into? Very straightforward, I can probably remove 1n and I can make it a b go of n solution. I'll try thinking of a big of n solution instead of a big of 2n solution.
Agreed? Agreed, right? So, what is causing this big of 2n?
This shrinking part. So, if I can trim down this shrinking because what is happening was, if you remember, when l was here, r was here, we ended up shrinking two elements. We ended up shrinking two elements so that it is a valid condition.
It is a valid condition. What if I say, I'll take this example. 2511010. I'll explain you.
array 2 5 1 10 10 2 5 1 10 10 and what is the value of k 40 whatever i say you you don't have to shrink it all the way let's understand what do i mean by that add a l add a r right and the summation was initially 0 and there was a max length initially a 0 and we started with the first element which is 2 right and after that what I did was I said is this segment valid and the summation was less than equal to 14 so I said it is valid and I updated my max length to 1 and right after this what I did was I took the r and I moved it to 5 so I added it 7 and again this segment was valid this window was valid so the max length get got updated to 2 after that I took the r and there was a 1 right so 7 turned to be 8. Is this valid? This is. So the max length was updated to 3. After that, I again took R and I took it to the next one, which is 10. And I added 10, it went down to be 18. And I'm seeing that this particular 18 is greater than 14. So it's an invalid condition.
It's an invalid condition. Now, some things to keep in mind. The max length that you have seen till now is 3, which is this segment.
What is happening after this? This segment is a valid one. And I added one more. So I increased the segment size to 4. And I'm checking if this segment size is valid or not.
Because I'm looking for max, max. So I'm increasing the segment size. I'm increasing and trying to check if it is valid or not. I'm saying this is not valid. So if I again increase it, the segment size will become 5. So I don't want 4 to like, I don't want 3 valid to go directly to 5. That's why I'm trying to shrink and bring it down.
But during shrinking, what I'm trying to do is taking out 2, which is basically making it 16. And I'm taking L ahead. I'm taking L ahead. And then I'm again taking out 5, which is 11. And then I'm taking L ahead.
So what I'm doing is I'm doing a two step. If it was a different problem, it might have been three. It might have been four steps. So this is where I'm consuming a time. Can I optimize this and say, hey, don't shrink it.
Don't shrink it. keep this particular window itself. I know one thing, I know one thing, a max length is 3. So why to shrink the window below this length?
Because that won't help me. Because if I take L over here, the window length will be 2. And then I'll again have to increase that 2, increase that 2 to a 3 size and then to a 4 size to get a possible answer, to get a possible answer. Because what I'm looking for is a possible answer, right? A possible length as an answer.
Length as an answer. So why to do that? Why to do that?
Yeah, if the question is asking you to find out the subarray, you'll have to do it. There's no other option. If the question is asking you, find out the subarray, you'll have to shrink it. But if the question is asking, find the length of the subarray. Do I need to shrink this and make it a length 2?
Ask yourself. Because if you make it a length 2, you'll have to increase it to 3. And then you'll get to 4. And 4 can be an answer. Because reaching to 3 is of no use.
Reaching to 3 is of no use. So this is what I'll try to use. If I've been asked to find the longest and not the subarray, not the subarray, just the length of the subarray, what I'll say is, okay, now I am at a length 3. Fine. No need to shrink it further.
No need to shrink it further. Just shrink it by 1. Because it got to a length 4, I'll just make it back to a length 3. And now again do the same thing. Now again do the same thing.
Take the R. to the next which is at 10, add a 26 and now check, is this 4 length valid? And it says no. Again shrink it by 1, take the 5 off, 21, take the L.
So what I've done is, I'm not allowing it to go beyond a length 3. I'm not allowing it to go beyond a length 3. I'm making sure I'm keeping the length 3 intact and if there is an addition I added, check it, no, come back to length 3, come back to length 3. Length 3, 3, 3, 3, 3. And eventually when it satisfies, it gets increased. It gets increased. Got it?
So it's not mandatory that you shrink back to a length 2. You can shrink back to the length 3 because I don't care about a length 3. I need a better answer than 3. So I'll check for all the length 4 that is possible or not. All the length 4 beyond that. All the length 4. And if any length 4 is possible, again start.
to make it length 5, length 6 and so on. So the optimization that will happen is instead of writing a while loop You can remove this and you can say, instead of shrinking it all together, just check for 1. If it is greater, if it is greater, just move it by 1. Keep it to the max length and then increase R and check for the next length. So while turns to if and if you do this, this big of n will go off. Yes, this big of n will go off and it will be a big of n complexity. And you'll see me doing this in most of the problems for the optimal solution.
But again, I'm repeating. if they're asking you to find the subarray, you can't do it, you'll have to get back to the value loop. Because subarrays, again, you'll find a subarray, but that might not be the correct answer.
For an example over here, this is a valid answer, right, which is 5 plus 1, 6 plus 2, 8. But again, if I just turn it back to 7, this is also a valid answer with a sum 13. So maybe I'll prefer this one. Maybe the question would ask you, find out the longest subarray with maximum sum lesser than equal to k. So you'll figure out this one is needed.
So again, if they're asking you to store, you'll have to think what are the conditions. Can you use if or not? That is very important.
If they say there are multiple answers and you can just print any one of them, that's fine. You can use it. Or if they're saying that, no, you have to print according to the condition that. Then it might not work.
That's the second pattern. So let's talk about the third pattern. And the third pattern is, it'll be given to figure out the number of subarrays with some condition, where some condition. So it's a very different problem. It's a very, very different problem.
It says number of subarrays, right? So this kind of problem, you'll be, you'll see that I'll be solving a lot. of them. This problem will be solved using the pattern 2. Remember this, using the pattern 2. It's very difficult to count the number of subarrays and when I solve those problems, you'll see why it is difficult. I'll show you examples and I'll show you why it is tough to understand when to expand and when to shrink.
These kind of problems will be solved using pattern 2. So it's very important to understand pattern 2. So Let me give you an example. I'll just go down and imagine I'm asking you, hey, can you figure out the number of subarrays with sum equal to k? Imagine this is the question.
So typically these kind of problems, I'll not be solving this, I'll be solving this in that video. Typically these kind of problems will be solved in this way. Whenever I see a number of subarrays, I'm not asked to figure out the length. number of subarrays and when there is a constant condition, it's a very constant condition. So, whenever there is a constant condition, it's very tough to realize, tough to understand whether to expand or whether to shrink.
It is pretty impossible to determine. So, in such scenarios, what will happen is, they'll break this problem into two things. Find out the number of subarrays where sum is less than equal to k.
This is how we will be solving. Sum is less than or equal to k. And then you again find out the number of subarrays where the sum is less than or equal to k minus 1. This is what you'll do. And once you've figured this out, you basically do a subtraction. Imagine this is x, imagine this is y.
So the answer will be x minus y. Always, always. You'll see me solving this.
And this particular problem. can be solved using the pattern 2. I'll be solving a bunch of them. Do not worry, I'll be solving this exact problem itself.
So that will be the pattern 3. Now the next pattern is pattern 4. Pattern 4, which is finding the shortest or the minimum window or length, whatever they can call and then the condition. Again, this is also very rare. rare case scenario you'll not be finding a lot of problems in it. I'll be solving one problem to explain you. It's pretty much identical, pretty much identical.
So what we typically do is, I'll just give you a overview and when I solve that problem in that particular playlist, you will understand. So what we typically do is, we take an L and R, right? And then we move R and imagine this turns out to be a valid window.
this turns out to be valid window right What am I looking for? I'm looking for a minimum size. So once I've got a valid window, what I try to do is I try to shrink, I try to shrink, I try to shrink, I try to shrink and check is this a valid window or not. I try to shrink, shrink, shrink the window and I try to check that shrinked window is a valid one or not and the shortest shrinked window, whichever is valid, I store it as an answer.
typically whenever you asked as a minimum you just get the window which is valid and then you shrink to figure out the smaller part we'll be solving the problem do not worry about that but the overall every problem will be revolving around generating all the subarrays expanding and shrinking and then using the if condition to make sure you're not shrinking it by too many places just by one place just by one place So overall this is very important. Keep this template, sorry my bad, keep this template in your brain because you're going to use it to solve most of the problems. So this was more like an introductory video.
It gave you an overview of how two pointers and sliding window are and most of the problems will be around this. You don't have to think a lot. Once you solve all the problems, I think we'll be solving around 10 to 12. I'm not sure.
I'll be solving around 10 to 12. Once you solve. All of these problems, you will be very much comfortable when you are appearing for an interview or for a coding round for that case. So this will be it for this one. So if you're still not 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 play some other video.
Bye.