All right, guys, here is our life changing observation and we have Max Air of left.
I noted that for some left point there, right.
If I move the left pointer of the Sabari at some position, mux air of that left is going to be the
maximum air pointer such that our sabari is valid and the observation is max error of left plus one
is always greater or equal to Mark's error of left right.
So what is basically means is that if I have a left pointer, let's take this example right.
If my left pointer is here and here it goes, one five to one and that's it.
This is Edes Mux Air.
So this is basically Mock's air of one.
Right, because I can go to seven the number of these things that I mentioned before.
So if for this left, the marks there is here, if I go, we've left plus one.
It's Mock's there is only going to increase, like for this example, marks are is going to be still
here, right?
Right.
When I come to the left here.
Now, what do I do?
I have two distinct elements.
So I can take seven.
Two, I can take two, I can take one.
And the marks are is going to be here.
And this is actually the solution of this example.
Right.
Because each time I go from the left pointer to the left, plus one pointer, basically my Southbury
got reduced to some number and this number could now not appear in my new current SOUTHBURY, which
is very great because I got room for more numbers so the R could only increase.
So now that we have understood what this observation is and what it means, how can we use it to reduce
the complexity from bigger and squared to linear time?
Bingo.
And this question has a very simple answer.
The first step is that I want to know the marks of one.
So the left is going to be, let's say, left.
It's going to be initially one.
And I want to know marks are.
And for that it's actually pretty simple because I am going to make a full loop, right.
We have right from one to end and for each new right, I am going to add this element into the frequency.
Right.
So odd.
To the frequence, I'm going to check, obviously, if the country's good or not, and as long as the
counter is less or equal to Kate, I'm going to continue, right.
So if the counter is greater than Kate, I will stop.
And then I will have our minus minus, right?
So this is a first for a group in order to find the marks are for left equals one, and they have all
the elements from position one to position marks are of one in my frequent survey, and they have my
Kondor.
So what will I do?
Well, instead of two, for most it looks, as we said, I am going to just have one nested loop for
left from position two to position M and for each new left.
Well first of all, my salary is not reduced by the element left minus one.
So I am going to delete.
OK, delete.
Eight of L minus one from the frequence, so again, when I delete an element from the frequency, I
decrease its frequency and if that frequency becomes now zero, that means that element doesn't appear
anymore in the subarea.
So I just make conterminous minus.
Right.
So after I delete this element, the previous one, I now have to check.
All right.
Maybe for this new left, the marks here could be greater.
So I'm going to increase the rate as long as I can.
And here I'm going to have a while loop.
So I see what.
The right pointer is less than and so I can increase it.
I will do it right.
I'm going to go right plus plus then I am going to OD element or into my frequence.
Right to my frequence.
I do that.
And after I got this last element to the frequency, there is the possibility that none of the number
of distinct elements is greater than key.
So I have to check if counter.
Is now greater than K.
Obviously, I will stop, so whenever this while loop finishes execution, I have two possible outcomes.
The first one is that R is now equal to M. So I can't hold it anymore.
But does Sabari is valid or the Sabari is not valid anymore and they have to decrease the R because
the last are obviously at the counter rater.
Blanchet So I'm just going to check if.
The counter is greater than K, that means it was the second outcome.
So what will I do where I am going to?
The lead element are from the frequence, obviously, so delete a R.
From the frequence, from the frequence, and then I am going to R minus minus, right.
All right.
As if the counter is good is less or equal to K.
Well, what does it mean?
It means that for this left pointer, the right pointer is not one position, and so for the next left
pointer, for each of the next left pointers, the arc is going to remain intact.
So this is obviously the maximum length SABERA that I am going to obtain now or in the future.
Right.
So I will update.
Answer.
And I can even break the program, right, because every solution that I'm going to find next is going
to have land that's going to be less than mine.
And this is how we get from the brute force approach and bigo of Land Square to the linear approach.
If there are some of you who can't understand or can't see why this solution is linear time, it's perfectly
cool because it's not obvious at all.
And we are now going to analyze the time and memory complexity for the time complexity.
I want you to think a little different.
And we know that we have a for loop and the inside the for loop, we have another wide loop.
So this might seem like, OK, isn't this big go off and square too.
And it's not because we are not going to look at the code, but the mentality behind it and the mentality
is the next one.
The left pointer obviously is going to move from position to position and so it makes and steps.
But for each left pointer, I have a right pointer, which makes some steps too.
But let's take a look.
If we have the left pointer and carefully moving from position one to position M, and this is good
with the right pointer and doing exactly the same thing, the right pointer is initially going to start
a position.
One is going to be increased, increased, increased, increased, increased.
Right.
So I have the first Vialet right pointer for the left pointer equals one and after that for each new
left pointer when left moves from some position to the next one, the right could only go forward.
All right.
So the right is only increased.
So basically the left and the right are going to be initially, both of them at one and from the execution
of the problem, they only are increased.
The left will make maximum and steps, obviously from one to end.
All right.
In this group.
And the right pointer is going to make a maximum and step starting that one going initially.
And then with every execution of this wide loop, it will increase until and each time this left pointer
or this right pointer is increased, we are only making some operations on the frequency array, either
by the insertion or deletion.
And we know that that operations are going to be performed in constant times.
So big of one.
Right.
So our time complexity in total is going to be the number of times the left is increased, plus the
number of times when the pointer right is increased, which is from one to end bigo of F and the memory
complexity is going to be our array plus the extra frequency array.
And because all the elements are between one and and the other is going to be STACEYANN.
So memory and then complexity for these solutions are people of that.
I really that understood the solution.
This I find it amazing.
It is very, very okay if you didn't understand it from the first go.
And right now replay this video and ask in the Q&A section if you have any questions at all and they
can do to in the next few days.