Hi, everyone.
So in this video, we're going to solve this question jump game two.
So basically this question is a modification of the old question that we have done.
So in this question, what we have to do so instead of telling instead of returning, true or false,
whether I will be able to reach the last looks or not, I have to return the minimum number of jumps
to reach the last index of this example.
So we consider this example in our last problem also.
So I told you, there are two ways to reach the last question first, which is basically take a jump
of one, then take a jump of three.
So how many times are required to jump sideward?
But if it will take a jump of two, then you will take a jump often, then you will take a jump, often
one.
So in this way there are three jumps required.
So what we have to do, you can see.
So we have to reach the last indexing, the minimum number of jumps in the number of times I have to
reach the last index and I would return the minimum number of jumps.
So the number of jumps are too.
So among the entry two is the minimum.
So my answer in this case will be two.
So two is my answer.
Two is the minimum number of jumps that I will require.
Now let's see how we can solve this problem.
So let us take a big example to understand the situation, one, four, three, seven one, then let's
say I have two, six, seven, six and 10.
OK, so initially I'm standing here and I want to reach here.
So let us take two variables.
Current ladder and basically the biggest current ladder and biggest ladder.
OK, so for one, the biggest ladder is basically I will be able to reach for four four and what will
be the biggest ladder.
So it will be I will be able to reach to OK from four I will be able to reach two.
So this is the biggest ladder.
Four four four three.
What will be the biggest ladder.
So this will be the biggest ladder for tree.
Four, seven, so this is one, two, three, four, five, six.
And then seven, so four seven, this is the biggest letter for one.
This is the biggest letter for two.
So this will be one and two.
OK, now for six.
So one, two, three.
And then four, five and six.
Now 47, so when two, then three, four, five, six, seven, OK, and similarly for 10, so one,
two, three, four, five, six, seven, eight, nine, 10.
So these are the biggest letters for all the elements.
Now, initially, I am present at the current letter.
OK, so initially I will be present at this letter.
I am present at this letter.
Now what I will do so I have to return the minimum number of items.
Right.
I have to minute number of jumps to reach the last index.
Now let's see.
So I am standing at one.
OK, so I will traverse the current letter now.
As soon as the current letter will finish, what I will do, I will jump to the biggest letter at this
point.
So jump.
I am taking a jump to the biggest letter at this point.
So at this point I have only one letter, OK, at this point I have only one letter.
I do not have many options otherwise, but I will do I will choose the biggest letter.
OK, so basically the idea is jus biggest letter.
So at this point I have only this letter available to me, so I will take a jump to this letter.
Then what I will do, I will traverse this letter.
OK, but it was this letter.
Now this letter has finished.
So at this point, what is the biggest labor?
So this is the biggest lead at this point.
OK, so at this point.
What ladies are available to us, so I have this letter available to me and I have this letter available
to me, so I have to let those available to me at this point.
OK, at this point, I have two letters available to me and I will choose the biggest letter.
OK, so this is the bigger letter.
OK, this is the bigger one.
OK, so this is bigger than this.
So I will make a jump to this letter and not this one.
Now, finally, what I will do, I will reverse this later.
OK, I will traverse this letter and I will be able to reach the last index.
I will be able to reach the last index.
Now, what will be my answer?
The answer will be how many jumps I took so many times I took.
So this is jump when this is the second jump.
And obviously initially I was present at zero, so from zero to the current level.
So I took three jumps, OK, I took three jumps.
Now you can see yourself what will be the answer from when I will reach four from four, I will reach
seven and from seven, I will be able to reach 10.
OK, so this is jump one.
This is jump, too.
And this is jump three.
OK, so my answer is correct.
So our side is correct.
OK, let's take one more example, let's take the example of.
This one day did Corven, so do three one one four two three one one four.
So two, then three, then one, then one and then four.
So again, first of all, we will find out the biggest later for everyone.
OK, so for two, what is the biggest lie that I will be able to reach?
One.
So from three, what is the biggest lie.
So I will be able to reach for.
For one, the biggest lie there is this one for one, this is the biggest letter and for the last six
days only to find out the biggest letter, not initially, one jump.
To go to the current leader, OK, then I will I the current leader now at this point.
How many ladies available to me?
So I have two ladies available to me, this one and this one, and obviously I will choose the biggest
one.
OK, so I will choose the bigger one.
So I will take a jump to this later.
And now I will traverse this ladder and I will be able to reach the last index.
So how many times I took so I took the first jump and this is my second jump.
So I took two jumps.
So this is jump one from two to three.
OK, so this is the first jump and this is the second jump.
So I am taking two jumps and I'm traversing two letters since I'm traversing two ladders.
I'm trying to listen to is my answer.
OK, and the jump is also to say that approach is correct.
Now, in the above example, you can see how many ladies we have traversed.
So this is the first letter that we have.
OK, so this is the first letter that we have produced.
This is the second letter that we have traversed and this is the third letter that we have traversed.
So in total, we try to three letters.
So the output is three.
OK, let's take one more example.
Now, in this example, we will not be able to reach the last index.
OK, so this is three, two, then one, then zero and then four.
So what is the maximum indicator they can reach?
So the biggest letter for three is basically to reach a zero.
So four to I can reach zero for one, I can reach zero four zero.
I can not reach anywhere.
OK, so let us start reversing the first letter.
OK, so I'm traversing the first letter.
Now, at this point, no ladder is available, no ladder is available, since no lead is available and
I am not present at the last or next, I am present at the second lesson because I am standing at the
second largest index.
So since there is no ladder available to us.
So in this case I will return.
Let's minus one.
OK, our default answer minus one means I'm not able to reach the next sample.
So I hope you understand the logic.
Now let us write the code.
So now let's ride the cold.
So in the jump that Burnham's.
OK, so let's change the name, the name is a.
OK, so let us find out the size first.
So this is a nazis'.
So if the value of any is one, that means there is only one index.
So how many jumps we need?
So the first index is also the last index.
So I need zero.
James.
Now, one more thing.
So basically, if the first index zero.
If I had the first index, zero zero percent, that means I cannot reach the last index, I cannot take
any jump, so I return minus one.
Now, what is the letter?
So initially the letter is physical, OK, initially I am, but I will tell us the letter.
Is it?
OK, so what this letter will contain.
So it will contain that letter, which I will provide.
OK, so letter of zero.
How many states are present in this letter?
So how many states are represented in this letter, so if 06 are present in this letter?
OK, and initially I have to initialize the jump variable to one, OK, not zero.
It will be one.
OK, you can see.
So you can see.
So this is the first to jump basically.
OK, this is the first jump to jump to the first letter.
So I have the initial I have the jump variable to one.
OK, my answer will be present in the jump.
So the jump is one.
What is current, what is still so Steyr is basically my current leader.
The state is basically the current leader and this leader variable, and it is the biggest leader,
OK, the biggest leader or I can say the maximum eligible index.
The maximum eligible index, so a jump is one.
Now, let does iterate over the area, so I will start reading from one.
OK, so I listen in and I placeless.
Now, what we have to do, so check, so if the value of A is basically and minus one, that means I
am present at the last index.
So since I am placing it looks like inadvertently jumps.
OK, I can return the jumps.
Now you're standing at a and you're five plus elfy is greater than the maximum eligible index, if I
a selfie is greater than the maximum reachable index, then you can update the maximum reachable index.
OK, then I will update my maximum reachable index.
Otherwise.
So what I'm doing, I'm proposing the current leader, so I traversing the whole state minus minus what
I am doing, I am proposing the current leader.
So for travelling the country later, I have to do stator minus minus.
OK.
So I'm traversing to let them know if.
The state becomes a zero.
So what is the meaning?
So if the state becomes zero, that means the current leader has been finished.
OK, so.
Currently, they're finished.
That means I need to make a jump.
OK, so I need to make a jump.
Jump?
Jampolis place, so you can see so if the current ladder finish, if the current ladder finishes, so
at this point, the current ladder finish.
So I need to take a jump.
So that's why.
Jump.
Plus, plus.
NetWare jump plus plus.
And in the variable ladder.
So what this little variable is containing it is containing the maximum Ridgewell index.
So this does not exist.
So here I told you to choose the biggest later.
But how I am writing the code, I am writing the code in such a way that this letter does not exist.
There is only one letter which is existing and this one letter.
OK, there exists only one letter, which is this one.
OK, you can see I'm updating the lighter variable.
OK, so I'm only maintaining Voloder, I'm not maintaining many.
Let us suppose you are present here.
So I'm writing the code in such a way.
So here.
For the logical explanation, you can understand there are two leaders.
But I am ready to going in such a way that the bigger lie that will exist.
OK, so if this is the bigger, lighter, then only bigger will exist and the smaller one will not exist.
So at this point, when you will take a jump, only this one letter will exist.
OK, only this letter exists.
So how many ideas I have to cover so I will subtract this from this.
So this one is the current position.
And this one is basically the mixing ritual index, so how many states will be there?
So the current leader has been finished.
You have to take a jump to the next leader.
So that's why jump placeless.
Now in the current leader.
How many states have to cover some 72 index minus the current index, the index are to which I am standing.
OK, simple one.
Now, if the current level is negative.
If the current leader is negative, that means I will not be able to reach the last Nixa written by
Nelson or otherwise if this thing is not clear.
What can I write here so you can write?
So would you can ride so if the current index is basically denied equal to the maximum reachable index,
if the current index is good, then all goes to make some reachable index, that means I will not be
able to reach the last index or return minus one.
OK, simple.
And similarly, you can return minus one here.
OK, you can return minus one here.
So we are returning jumpier.
OK, so this is the complete code, so what I'm doing here is.
So I have this little variable.
I have this.
So let's take this example, two, three one one four.
OK, so two, three, one, one and four.
This is a zero one, two, three and four zero zero zero zero zero.
So let me they make some ritual index.
So initially they make some ritual indexes, basically index to and the jumps and the stair is basically
to jump is one.
OK, so take the jump.
Jump is one.
OK, Step decided to I'll get Tuesday's Venstre dustier.
Now, I did so at three, the maximum level index becomes four.
OK, I can reach the index four.
So what I'm doing, I will update the ladder.
So this is my letter.
This is the biggest letter, so for one, the maximum literal index is basically this one.
But what I will do, I will maintain only the bigger one, so I will not maintain this one.
This one does not exist.
Similarly, for one, this is the letter.
But this letter is very small as compared to the Slagel.
So this letter does not exist.
So I have only to learn this one and this one.
So what will do?
I will try this letter.
Then I will take a jump.
And the jump will become, too.
And finally, I will traverse this letter, the value of I will become minus one and then I will return
the jump.
So I will return to OK, I will return to surplus.
My answer.
So at this point, what happen?
So at this point with a value so state is to then I will come here today minus minus two will become
one.
Then at this point state will become zero, so stay minus minus if the state becomes a zero.
So at this point I do next to the state will become zero.
Then you need to take a jump.
I'm taking a jump then.
But I am doing how many states I have to cover.
So this is labor minus I.
OK, so this is like the minus eight.
The value of letter is basically next fall.
So it makes four minus the current index which is two, so four minus two is basically two.
So two is the value of the status.
OK, you can see I have two.
This is two.
OK, so this distance, this distance is basically two.
So that's why the value state is basically two.
Then you will come here.
The value state will become one, then you will come here and I equals N minus and you will return,
jump and jump is basically to OK, so this is basically hard question.
OK, I know it will be difficult to understand.
But once you will go to the court, you will be able to understand it in a much better way.
OK.
And if you notice in the question says, we can always assume that we will be able to reach the last
minute, but we have written code in such a way that you can see I am returning I am writing code in
such a manner that if I am not able to easily lost and I will return minus one.
OK, so you can remove this assumption.
OK, we have written code in a good manner.
Now let's have a court and then we will submit.
Now, let's have it so what will with the time in the space complexity of our solution?
So our goal is working fine, so the time, complexity of our solution is basically big golf and.
And the space complexity, we are just creating only a few variables.
So this is big often.
OK, so this is finally the time and the space complexity.
So this question is actually a hard one.
OK, so it will take time for you to understand.
So just go to the diagram and they will be able to understand it in a better way.
So there are many ways to solve this question.
OK, I think this one approach is better.
This is a good way to understand the question.
Thank you.