What's up, guys?
Andy here and we are starting from zero to hero journey.
I've chosen the perfect problem to be the ice breaker of the series because it has a super simple idea
behind it, but it can be tricky.
So this problem could be tagged as an array problem or even a dynamic programming one.
But it's actually very natural.
So it's called D as Y loves sequences and let let's read the statement together.
So the design has a sequence A consisting of M integers, which is actually an array.
Now we'll call a sequence A.I. A plus one dot, dot, dot.
A.J., we have a less or equal than J subsegment of the sequence eight.
So basically this is a Saberi, right.
This is the definition of us out there right now.
The value J minus a plus one denotes the length of the subsegment obvious.
Your task is to find the longest subsegment of a such that it is possible to change at most one number.
Change one number to any integer you want from that subsegment in order to make it strictly increasing.
And you only need to output the level of the subsegment you find perfect.
So I basically have an array of N elements and I should choose a Starbury which is valid and a valid
sabari means that I can change only one element, Max, from that SABERA to any integer I want in order
to make the savary steeply increasing, which is quite nice.
Now let's check this example and we are going to be simplistic here and we are going to use the notepad.
So I think I've returned.
Oh, I've written some notes here, but let's starting all over again.
And our array.
Let's see what values it does.
Seven, two, three, one, five, six.
Right.
So for this, the answer is five.
Then why is that?
Because our solution is actually this summary from position to all the way to position six.
And if I take this Vella's.
It's obvious that I can change the one to a four.
And now this Sabari is strictly increasing, right?
So here, let's say here, my answer is going to be five, which is perfect.
Now, let's take the initiatory and think about this problem.
Right.
So seven to free one.
Five and six.
Perfect.
Now, what I always like to do is, first of all, look at the restrictions of the problem.
And I see there that the first line contains an integer M, which is less or equal then than a par five.
Which means in order to have an acceptable solution.
Right.
I can't have a brute force approach in B go off and squared.
That's way too large.
So I need to be smart about this.
Now, if I want to, let's say, have a brute force approach, that's actually quite simple, if you
think about it.
Because when you have an array of size n how many distinct Subedar raise this array would have.
And the answer is bigo of.
And squared.
So what I can basically do is fix that subarea.
So I should fix the left pointer.
Then I should make another for loop leupen fix the right pointer.
And I should check if only one number is.
Let's see the missing piece of the puzzle.
Right.
So it's going to look something like this, as I've written there.
So a brute force in Bigo of an squared is going to have the first for loop, which is going to fix me
my left pointer.
So starting with position one all the way to position.
And plus plus, by the way, we are going to put this in port.
Rocks.
But this is just for the fun of it.
For the brute force approach in not.
Let's say.
So if I have here the left point there.
OK.
Let's open some records.
And what shall I do?
Well, my subarea is going to start at position left.
So I should go as long as I can.
As long as these Saberi from left to, let's say, appointer right, is directly increase.
Right.
So I shall go with my right pointer starting from left.
PASWAN Right.
Right.
As long as right is less or equal, then.
And and one more condition very important in order for this to be strictly increasing.
Always a of rights should be greater, strictly greater than a right minus one.
And a of right is strictly greater than a of right.
Minus one.
What's wrong?
I don't always.
Right.
Bus pass.
So after this for loop.
Successfully finish his execution.
I have the left pointer, which is the beginning of my Saberi.
I go all the way until I find an element which is now which basically makes the Saberi invalid.
Right.
Which is less or equal than its previous version.
So that is the element that I should change, obviously.
Right.
So I should change it to some value, which is between the previous element and the next elements.
Right.
So if actual change here A of.
Right.
AOF right, the new aof, right.
Its new value, right?
Should be somewhere between a right minus one and a right plus one.
So let's be a of right.
Minus one.
Plus one.
And now from left to right.
Everything is strictly increasing.
But I should make sure.
Of one thing, this thing can happen only if a of right plus one is greater than a of right.
Minus one.
Plus one.
Right.
Because I don't know.
Let's take this example.
If let's say I had here free and a of right.
Which is the current element is free.
And let's say a right was on his for a candidate, because what I basically do is I see, OK, this
free is less or equal than the previous free, so I should make it at least four.
But when I make it.
For the next element is for two.
And that should be at least five.
Right.
So only if a of right plus one is greater than a right.
Minus one.
Plus one.
I can do this.
So what I have to do here is after I find the first missing piece of the puzzle, which is now a of
right.
I should check it.
First of all, if right.
Becomes equal to an.
That means that I should change that element and I don't have a next one.
So the whole SABERA is going to be valid, right?
So if right becomes equal to and let's say that's basically it and saw it's maximum between the answer
and and minus left plus one.
Right.
I change that element and that's it.
But if not.
Else I should be very careful.
I should check if a of right plus one is greater than a.
Of Right.
Minus one.
Plus one.
And if it is.
This is perfect because now I can change that.
A right to be a right minus one.
Everything plus one.
And I should go and check for the next elements for the strictly increasingly.
Right.
So what do I basically do?
Is that now I am going to start with my for loop.
So my right is going to start now from its previous value plus two.
All right.
So I know that a right minus one, a right and a right plus one are now okay with each other.
So I go from right.
Plus two again.
Right.
As long as right is less or equal than N and D a of right is greater.
Strictly greater than A of right.
Minus one.
And I just increased my right.
Perfect.
Now after this four loop finishes execution to let me make this a little wider so you can see after
this for loop finishes execution two, I know that the left is the start of the summary.
And now this right is the end of the longest valid summary, which starts a position left.
And I made only one change.
Right.
So now I will have answer is Max between answer and right.
Minus left.
Plus one right, minus left.
Plus one right.
So the race here is that this answer is initially going to be some variable initially equal to zero.
And this variable is going to hold my answer of the problem.
Right.
So the length of the longest valid summary.
And I always update this answer.
And in the end, I will return the answer.
So obviously, this is not the full code for the brute force.
But this is like it should.
This is like a blueprint.
All right.
This is how it's going to look in the end.
So for loop for left.
Go as long as I can find the first bad element, change that if I can.
And if I can, I go all the way until the savary is valid, when it's not.
I found the left or the right.
And I update my answer.
Perfect.
But remember, this is still a brute force approach.
So we are going to need a linear solution for this one.
Bigger of.
Right.
So our optimal solution is going to be a beagle.
And let's think about it.
For the bigo of and squared, we have fixed the left and the right pointers.
And then we have found basically by hand, by rating, we have our four groups.
We have found what is the bed element and changed it.
Now, if I want a solution in Biegel of an.
I can't fix both the left and the right.
Because there's too much time.
But I can fix and other information I can fix what is going to be the position of the bad element?
What is going to be the bad element that I'm going to change?
So let's call this position.
I can basically make a four group, let's say from B, we one P less or equal than N P plus plus.
Right.
So what I'm doing here, what this means.
This means that I am going I am going to change the value of a P.
Right.
So I suppose that that a B is the first bad element.
What does it mean.
What if a B let's say.
All right, let's write these elements A wanted to a free.
That that that a B minus two, let's say a B minus one.
Let's say a B, A of B plus one, a B plus two and so on until a n if this AP is going to be the first
bad element.
That means that.
Starting at position B minus one and always going to the left.
These elements are always going to be strictly decreasing right now.
Until some position left, let's see.
Right.
That if I look at the right of the element AP starting from position P plus one and going each step
to the right, these elements are going to form a strictly increasing sequence.
Right.
So let's just take the example with the seven two, three one, five, six.
If I take this seven, two, three, one, five, six.
Basically what I do here is I suppose that the element that I change is a positional four because this
is actually what happens.
So P equals four that when B equals four.
What do I know that starting from position free, I will favor strictly decreasing sabari.
And that's right.
If I look at position free, I have the value free, which is good.
That if I go one step to the left, I have an element to strictly decreasing.
Perfect.
Then if I go one step to the left, I get seven.
And here I stop because this is not strictly decreasing anymore.
So I have the Saberi two and three.
Then if I look at the right of position four.
Right.
I got five.
One more step to the right.
I got five and six, which is great, freakley increasing.
And then the array finishes, right.
So if I am to change the element of position for.
And make it the value that I want.
I can then add to this element.
I can, let's say, form the Saberi.
We've discernment with those elements in its left, which are strictly decreasing and those elements
in its right which are strictly increasing.
Right.
So here I choose to make this element of position for to be a value for.
And then I can union myself with the true free from the left and with the five six from the right.
And here is my area.
So my solution is going to be of land five.
Right.
So this is basically what happens when I want some position B, I should always know what is the length
of the maximum Southbury starting that position B minus one and always be secret decreasing.
And what is the length of the maximum Saberi.
Starting a position P plus one and always be strictly increasing.
Right.
So I'm going to need those informations.
And because I already fixed the position B, which is already of four groups or Biegel of N, I am going
to need those informations in Bigo of one in constant time.
And how will I get those in Konstantine that asks for a precondition.
So step number one.
I showed pre compute, right?
So pre compute, what should we pre compute?
Well, we have to information.
As we said, the first one is going to be let's call this.
I don't know.
Max left.
Right.
So Max left.
Max left the position.
This Max left is actually the maximum length.
Right.
Of the summary and let's call this Saberi.
Basically, it's going to start to position minus one and always go to the left.
So if its length is going to be L, for example, discovery is going to be from position I'm minus.
All the way to position a minus one.
Right.
So basically is going to be the max and the max m.
Such as the Southbury.
From position I, minus L two, position I minus one is strictly increasing, right?
So a Y minus one is greater than a of minus two, which is greater than a minus three.
And so on and so on.
A minus ab.
Right.
And this a minus cell is now less or equal than a of a minus L minus one.
Right.
So basically the maximum length such as those elements are always going decreasingly strictly decreasing.
Right.
And just as that the max.
Right.
Which is basically the same, but in the other direction.
So the marks l let's say, such as the SA bear rate.
Now it starts with position I plus one.
So A of a plus one.
And this is going to be less than a of IPASS two.
So I pass to less than a of AIPA free less than.
And so on and so forth until a of a plus.
And and that's it.
We should pre compute this Max left.
And this Max.
Right.
And why do we need that.
Because after we managed to do this, we are going to apply the step number two and the step number
two we've just discussed.
Are going to fix the position B of the element of the element.
We are going to change.
Right.
So figure this position B of the element.
We are going to change.
And if we fix that position, we should ask ourselves the following thing.
What can I always change this position such that it's going to be okay in the end?
And not always.
Because if I change the position B.
All right.
Well, I can use the Saberi starting at some position left until the position B or starting a position
B until some position.
Right.
But if I want to use, let's say, a Saberi starting a position left, which is less or equal, then
B, right or even less than B and B is less than right.
I should check one thing if.
A of A of B plus one, minus A, B minus one is greater or equal than two, because again, we have
the example in which let's say I have three, three and four.
Right.
If B is this element, this position.
However, I will change the B.
I can't have a sequence that will start at least here and end at least there.
Right.
Because if I changes to a four, it's still not valid.
If I use a five month vallet.
If I use it to an advantage.
Right.
So the property in order for this to happen smoothly, is that a of plus one minus a B minus one should
be greater or equal than two.
And if the difference is OK, then what is going to be my answer?
Well, I am going to if this is the position B, I am going to take the valid savary, ending that position
B minus one, which has Lamphere Max left of T minus one plus one element, which is my B, the position
B and then I'm going to take the savary starting a position P plus one, which is valid.
So Max.
Right of peoples.
Perfect.
This is.
So step number one should be perform in linear time.
And then step number two, obviously is linear time.
So how should we compute the marks left of AI and the max right of.
We will do this using a for loop for each of those.
So let's start with the marks.
Left, right.
I need those.
Sudbury's to be all right.
All right.
So think about it this way.
If I iterate for each element starting a position, one all the way to my position and I plus.
Plus.
Why do I have to do.
Well, first case scenario, if I is equal to one.
So is the first element of the array obviously.
Or a of AI is less or equal than a of minus one makes left of AI is going to be equal to one.
As simple as that couldn't be greater than one.
Right.
That's obvious.
As if it's greater than one and a Y is greater than ever minus one.
That means that Max left of AI.
He's going to be one.
So this current element plus the valid summary ending that position minus one.
So max level of minus one.
Right.
Is basically the continuation of that summary.
And this is for the max left.
For the max right.
So guess we are going to do the same thing, but we are going to start from position N and going to
the left.
Right.
So each time decrement in this I get.
If I is a position M or A of AI, is hope less or equal.
So is that what this should be.
Sikri increasing.
All right.
So and this one is greater or equal than a fibrous one.
Obviously, Max Right.
Of AI is going to be one and.
Max, right of I is going to be one plus max right of IPASS one.
And there's a solution, guys.
It's linear time, which is super good.
Now let's open our editors code box, create a new project and console application.
They use C++ and I don't know, let's call it S y strings or something.
Right.
So I am going to walk you through my implementation of this not.
What shall we do here is we, first of all, have to read this input, so we are going to remove this
line and read our array.
So, first of all, read it size, which is and then read each element.
We have a follow up.
Right.
So starting from one all the way to an eight plus.
Plus, we are going to read our array, which is a not.
Let me define those.
So an eight.
And Max.
And four.
And Max, I'm going to use a course integer and max of size.
One hundred thousand five.
Right.
So always make the size greater.
Just to be sure.
I indexed my arrays.
Starting a position one.
So I need at least one extra element for every array defined.
Right.
After I read this array.
What should I do?
Well, let's compute.
Max left and Max right.
As I said, actually, I'm just going to take the quote here because I don't see any use in writing
it again.
It's okay.
It's in there.
Let's indented.
Perfect right now.
We are going to compute this Max left on Max.
Right.
So let's define those two.
So here I have my max left.
And Max and my Max right off.
And Max to perfect.
Max left.
Max right.
Super good.
Now, after he computes, what will we do?
Well, again, I will take the code because it's time for the step two, which basically fixes me my
position.
All right.
So let's write this code for this one, actually, because I don't have it.
I will fix the element which I'm going to change.
So for position B from one all the way to N, B plus pass.
Right.
Let's think about this.
I want to change the position.
Well, when I change the position, be.
I can do free following.
Three possible solutions.
Right.
And those are.
I can start at some position left and go all the way to the position be.
Or for my answer, for my desire to subarea, I can start a position B and go all the way to some position.
Right.
Or the last possible outcome is I can start at some position left and end that some position right in
which obviously left is less than B, which is less than right.
So let's take the first case left B.
For this, what they have to do.
Well, let me do one thing first, because I should define my answer variable.
Now, it's OK.
I should update this answer to be the maximum between its current value and one from this element of
the position B that I'm going to change.
Plus, the marks left of B minus one.
And that's for the first possibility for the second one.
B and right.
I am going to update my answer to be the maximum between an answer and one plus max right.
Of B plus one.
Right.
So this is the possible the second possible scenario.
And for the first one, I should check if it's possible to have this outcome.
So a of P plus one minus A, B minus one is greater or equal than two.
And if it is possible, I'm going to update this answer to be the maximum between answer and guess what?
One for my element.
Plus, I'm going to merge this with the Saberi on my left, which is Max left of T minus one.
And with the savary on my right, which is much right of P plus one.
Right.
So Max.
Right.
Of B plus one.
Perfect.
And that's it in the end.
What shall we do.
We will just print our answer and that's it.
That's it of Nine Inch and Skold.
Fingers crossed.
Let's hope it compiles and it does.
And what was our example?
It was six elements, seven two, three, one, five, six.
So six elements, seven, two, three, one, five, six, five.
That seems right.
Perfect, guys.
This was the first video of the series From Zero to Hero.
I really hope that you enjoyed and understood my solution to this problem.
I think it's super beautiful and it's a very good problem to start.
And if you think these videos are useful and provide some value to you, make sure to keep the subscribe
button.
Make sure to hit that ring bell in order to be notified when I post.
Make sure to like the videos.
And the best thing that I could advise you is make sure you join our Facebook group, because I pray
to the mastermind in which I want to share one challenge a day.
I want to share some more pieces of advice from my knowledge and experience in competitive programming
and interview questions.
And we are going to grow to be a big community to help each other out.
So if there's something unclear about this problem and what my solution.
Make sure to post in the comments.
If you have any suggestions about what you'd like to hear me teach maybe or what kind of problems you'd
like me to solve.
Or maybe you have one problem that's really super interesting and you want me to help solve you and
posted down on YouTube.
I am super, super excited to hear about it both in the comments and I can't wait to see the next video.