Mastering Two Pointer & Sliding Window Techniques in DSA Interviews

so with this video we will be starting off with the 2 pointer and the sliding window playlist from the sters A2Z DS

course in case you haven't checked out our DSA course 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 uh 2.0 and the sliding window playlist so one thing this is not

a typical Al algorithm that you'll have to U 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 bunch of

problems on two. and sliding window but please please make sure that you watch this video till the end because you'll

understand uh the patters and specifically the template that we are going to reuse in most of the videos

across this particular playlist so we generically see four kind of uh uh patterns in this particular topic the

first one is uh where it's a constant window right U 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 uh given an array with positive and negative

integers given an integer k your task is to figure out the maximum sum that you can obtain 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 + 3 6 + 2 8 8 - 1 7 right so you 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 four 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 zero index first index second

index third index which is typically K minus one of 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 eight 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 one right where you can say that initially L is at the zeroth index R is

at the K minus oneth index you can run a loop from L to R and the summation that you'll get is -1 + 2 + 3 + 3 that is 7 3

+ 3 6 + 2 8 yeah seven so you got a sum of seven 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 has 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 uh you take off the last element and you

add up one more element so 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 before moving L you'll have to take out this minus one 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 doing that you can say sum equal to sum minus array of L right and the other thing that you can

do is l++ and that was with L what about R sum equal to first you have to do R ++ then

sum plus array of far simple that is what you have to 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 maximum 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 was pretty simple depending on the conditions you'll have

to do your job you can run a fall 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 uh not it will not be asked a lot of times uh we'll be

doing one problem on this one because I haven't seen it uh that much in interviews but still it's just good to

know the second uh type of pattern will be it'll be given something like longest subar

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 example longest subar matches the pattern longest subar

can be a substring if it is a string problem it'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 subar any consecutive portion of the array any

consecutive portion of the AR right maybe I can pick up this and this can be called a subarray whereas 1 and 10

cannot be called a subar because it is not consecutive a single element is is also a subarray the entire array is also

a subarray remember this okay so you have to pick out the 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 uh 7 + 7 15 7 + 7 14 + 1 15

whereas this is not lesser than the sum so this subar cannot be picked can I pick up the subar uh probably yes 7 + 1

is 8 + 5 is 13 and this is lesser than this one do you find any other subarray I typically don't find any like I I'm

not able to find any other subarray this is the longest subarray where the sum is less 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 return the

length of the subar it will depend on the question so in these question uh there's typically a three format uh 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 subar yes so a typical Brute Ro

force will be to generate all the subarrays and that's going to be the template you'll always generate all the

sub arrays 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 subarrays that is possible with that element and I know single element is

possible you attach five you attach one you attach 7 you attach 10 all the subar is 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 10 and that is the only one so you have to generate all the sub Aries how

you can do is because we going through each and every element what you can do is you can start from zero and you can

go on till n minus one 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 G goes here so you take one more then the J goes here so 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 one that's it and you're able to generate all the subar that is how you'll generate all the subar 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 Aries 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 subar and the sum is two then you attach five the sum is 7 then you attach one the sum is 8 then

you attach seven 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 zero 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'll have to add up this element please add up this element done and if

it did this you can straight away update max length equal to Max of max length comma what is the length of the

particular subar 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 + 1 very standard mathematics so what you'll do is G minus I + 1 done and that would 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 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 + 5 is 7 + 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 optimation 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'll big of n Square near about because two Loops are running and what about the space complexity over

here it will be beak of one 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 BR Force for the pattern number two 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 an 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 uh 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 the 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 okay 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 to 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 two is that lesser than equal to K because that is

the condition and I'm saying yes so if 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 generically what you'll 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 seven does this window satisfy the condition you say yes yes it does and if it does

you update the max length to two perfect again you can go ahead and do the next thing you can again op for widening the

window so this time this is the window that you're looking for and the sum will be updated to eight is this a valid

window this is because the summation is still lesser than equal to K so the length can be updated at any moment the

length of the window is Rus L + 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 + 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 the in this direction expanding you tried 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'll do is always shrink from the left shrink two you take out two so the moment you take out two the 15 balls

down to be 13 and this time the r moves ahead and you say okay this is the window and some 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 you

already have a l three so no need to update so you have to shring the window but over here you shring by one place

you Shing 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 the step

and imagine just imagine this is not seven 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 one which is two so when you take up two it gets down to 16 and the r sorry and the L goes

ahead this is the window you need to understand you have a 16 and this is the window not a valid one still violating

the condition so you rrrink it you res shrink it and you take out five now it is a valid one now this

is a valid one so you can again compare the length the length is two 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 R this becomes 21 which is not a valid so

you again shrink so 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 Z started with r equal to Z started with the sum

equal to zero started with the max length equal to zero 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 lesser 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- L + 1 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 a invalid

condition in such a scenario I will be taking sum equal to sum minus array of L I'll take out L and I'll move L = to L +

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 it 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 = to r + 1 after

this you'll 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're asked to print the subarray this is where you'll have to

store the L and r store L &r if you're asked to print the sub array because this is where the max

length is getting updated you'll have to store the L and in case they are asking you for the subar remember so what will

stay uh constant throughout firstly uh L andr is going to be constant in the template remember this max length

typically in all longest you'll have to have it uh this stays constant again uh this one is a condition based depending

on 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 beo

of n squ 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 right if R this R will at Max move from here till here that's a beo 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 up 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 n and the

shrinking will work for b n so overall it is B go of 2 N and what about the space complexity again over here it is

bigger of one 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 which is beo of 2 N now

this is going to be the better solution I'll have to optimize this now if you're looking at a big go to n how much

further can I optimize if the array is having 2 N elements sorry if the array is having n elements how much can I

optimize 2 N and two very straightforward I can probably remove one n and I can make it a b of n

solution and try thinking of a beo of n solution tion instead of a b of 2N solution agreed agreed right so what is

causing this B of 2N this shrinking part so if I can trim down the shrinking because what was 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 251 1010 I'll explain you

aray 2 5 1 10 2 5 1 10 10 and what is the value of K 40 whatever you see you you don't

have to shrink it all the way let's understand what do I mean by that add L add R right and the summation was

initially zero and there was a max length initially a zero and we started with the first element which is two

right and after after that what I did was I said is the segment valid and the summation was lesser than equal to 14 so

I said it is valid and I updated my max length to one and right after this what I did was I took the r and I moved it to

five so I added it seven and again this segment was valid this window was valid so the max Len get got updated to two

after that I took the r and there was a one right so seven turned to be eight is this valid

this is so the max length was updated to three 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 a invalid

Condition it's an invalid condition now some things to keep in mind the max length that you have seen till now is

three which is this segment what is happening after this this segment was a valid one and I added one more so I

increased the segment size to four 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 five so I don't

want uh four to like I don't want three valid to go directly to five that's why I'm trying to shrink and bring it down

but during shrinking what I'm trying to do do is I'm taking out two which is basically making it 16 and I'm taking L

ahead I'm taking L ahead and then I'm again taking out five which is 11 and then I'm taking L head so what I'm doing

is I'm doing a twostep if it was a different problem it might would have been three it might

would 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 my max

length is three so why to shrink the window below this length cuz that won't help me because if I take L over here

the window length will be two and then I'll again have to increase that two increase that two to a three size and

then to a four 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 two ask yourself because if you make it a length two you'll have to increase it

to three and then you'll get to four and four can be an answer because reaching to three is of no use reaching to three

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 subar not the subar

just the length of the subarray what I'll say is okay now I am at a length three fine no need to shrink it further

no need to shrink it further just shrink it by one because it got to a length four I'll just make it back to a length

three and now going do the same thing now again do the same thing take the r to the next which is at 10 add at 26 and

now check is this four length valid and it says no again shrink it by one take the five off 21 take the L so what I've

done is I'm not allowing it to go beyond the length three I'm not allowing it to go beyond a length three I'm making sure

I'm keeping the length three intact and if there is an addition I add it check it no come back to length three come

back to length three length three 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 two you can shrink back to

the length three because I don't care about a length three I need a better answer than three so I'll check for all

the length four that is possible or not all the length four beyond that all the length four and if any length four is

possible again start to make it length five length six 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 one if it is greater if it is greater just move it by one keep it to the max length and then increase

on and check for the next length so while turns to if and if you do this this B of n will go off yes this B of n

will go off and it will be B go of n complexity and you'll see me doing this in most of the problems for the optimal

solution but again repeating if they're asking you uh to find the sub array you can't do it you'll have to get back to

the while loop because subarray is again you'll find the subarray but that might not be the correct answer for an example

over here this is a valid answer right which is 5 + 1 6 + 2 8 but again uh if I just turn it back to

seven this is also valid answer with a sum 13 so maybe I'll prefer this one maybe the question would ask you find

out the longest subar 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 a form 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 but if they

are saying that no you have to print according to the condition that then it might not

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 sub arrays uh with some condition where some condition so it's a very different

problem it's a very very different problem it says number of subar right so this kind of problem you'll be uh you'll

see that I'll be solving a lot of them this problem will be solved using the pattern two remember this using the

pattern two it's very difficult to count the number of subar 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 two so it's very important to understand pattern two so

typically let me give you an example 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 a

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 subar I'm not asked to figure out the

length number of subar and when there is a constant Condition it's a very constant condition so whenever there's a

constant Condition it's very tough to realize tough to understand whether to expand or whether to shrink 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 lesser than equal to K this is how we will be solving sum

is lesser than equal K and then you again find out the number of sub arrays

where the sum is lesser than equal to K minus 1 this is what you'll do and once you figured this out you basically do a

subtraction imagine this is X imagine this is y so the answer will be xus y always always you'll see me solving this

and this particular problem can be solved using the pattern two 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 three now the next pattern is pattern four

pattern four which is finding the shortest or the minimum window or length whatever they

can call and then the condition again this is also a very rare rare case scenario you'll not be finding

a lot of problems in it it'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 uh so what we typically do is we take an l and R right and then we move R and imagine uh 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 owner I try to shrink shrink shrink the window and I

try to check if that shrink window is a valid one or not and the shortest shring window whichever is valid I store it as

an answer so 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 a problem do not worry about that but the overall every problem

will be revolving around generating all the sub Aries expanding and shrinking and then using the if condition to make

sure you're not shrinking it uh by too many places just by one place just by one place so overall this is very

important keep this this uh template sorry my bad keep this template in your brain because you're going to use it to

solve most of the problems 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 uh 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 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 play some other video tell them why take

care Bren golden I