But some guys this is Angel, a computer science teacher for today.
And in this video, we are going to learn a super important technique, probably the most important
when it comes to solving problems with a race, which is the sliding window technique.
And the sliding window technique is a technique that's usually used when we have to deal with problems
that ask for the optimal sabari.
OK, could be the maximum length SABERA with some property or the minimum cost subarea with some property.
And the cost is defined.
Depends on the problem.
Right, or could be even the number of subarea of some property.
And so in general, we should start with a brute force approach in which we make a for loop for fixing
the left pointer of the summary and then make on the formula for fixing the right pointer of the Southbury.
So basically trying out each Southbury and then based on the property that that Sabari should have,
we can make an observation that when only one point of the subarea, let's say the left pointer moves
in some direction.
All right.
So we make a forward and fix all its possible value as the right pointer will move in the same direction
on the same time with the left pointer, too.
So that extra for loop is useless and we are going to move the right pointer along with the left pointer,
thus reducing the time complexity from Bigo of M squared to only Biegel of if this is too much for you,
don't worry.
We are going to solve right now or problem example to understand this technique better.
So without further ado, let's take a look at the statement.
Given an array of natural numbers, we should find the longest sabera.
We've got the most distinct element.
So now this.
That is the kind of problem that we've talked about earlier where we should find an optimal summary
of some property.
Right.
In our case, that optimal means the longest Southbury.
So the maximum length and the property means that it should have the most distinct elements.
So after some time and experience, when you are going to read these kind of statements, you are instantly
going to know that, OK, this is probably a sliding window technique problem and then you get used
to it.
We are going to start solving this problem with a brute force approach and the brute force approach
is going to have the time, complexity of bigo of square.
Right.
So Brute is going to be big and square.
And you probably guessed this big goal of M squared is going to be for the two four nested loops, the
one for the left pointer of the savary and the other one from the right point.
So we are going to start with the first for loop, which is for the left pointer.
Right.
So I am going to fix my left pointer.
All right.
Which is going to be from one to end and so on.
Let's say my left pointer is here and I want to move.
We have the right pointer from left to the end of the year.
And while moving with this right pointer, I should know how many distinct elements I have in my current
salary.
And we know how to solve that now using the frequency.
So for the simplicity of the problem, we are going to assume that these elements are between one and
end.
Right.
So we can use that frequency because we haven't studied yet another map.
So I am going to make this room for left and for each new left, I am going to reset the frequency.
So it's now clear no elements in it.
And obviously, as long as I move with the right pointer from left to right point, the right point,
the right pointer at each new element, I am going to add it in my frequency array.
And when I'm at some right point and I see that OK from the frequency range, I know that the number
of distinct elements isn't key anymore.
There are more than eight distinct elements.
I know that I should stop.
And for this left pointer, the biggest the right pointer so that this Sabira is valid is going to be
the current pointer minus one.
So the on big lines is going to look something like this for I'm going to have the left from one to
and so for each new left here, reset the frequency.
All right.
So reset the frequency.
All right.
Which is super simple to do because for I if I from one to end its frequency should be frequency of
I should be zero.
I am going to need another variable to count the number of distinct elements.
Right.
So for each left again, I am going to have a counter equals initially to zero and then the nested four
group we rights or four.
Right.
Which starts at left and goes to N and for each new element I am going to add it into the frequency.
Right.
So add to the frequency.
All right.
And whatever I added to the frequency.
So what I basically do.
Is F R of a r.
Here plus plus, I should check if after I increase it, right?
So after this half hour plus plus if it's equal to one, obviously this element is new.
It's the first time it appeared.
So I just counter.
Plus plus after this, I should just check.
All right.
If let's say.
The counter is OK, right?
So if counter, let's say, is less or equal to OK, I just have to update the answer.
All right.
And for doing that, as is the maximum from answer an R minus five plus one.
Right.
So this is how the code look for the brute force approach.
But for the optimal solution, we are going to take this brute force approach, make a simple observation
and reduce it from Vago of M squared.
To actually.
Bigo of that, let me clean the whiteboard and let's make that observation.