Hi, everyone.
So in this video, we are going to solve this question jump game, so what is the question?
So what is the question?
The question is very simple.
You will be provided with a non-negative integers.
That means positive integers, including zero.
So you have an array at different ages and you are initially at the first index.
OK.
So this is the first index and this is the last index, initially, you are first index initial evaluation
that the first index of the area.
Now each element in the area represent the maximum jump that I can take.
For example, if let's say this is two.
OK, so this to me is I can take a jump of one or I can take a jump of the maximum.
I can take a jump of two.
So basically.
Let's say the name of this ad is basically name, so number five means the maximum jump I can take is
basically name of a.
So and these jumps are also possible less than a Muffie.
OK, and we have to remain whether we can reach the last position or not.
Let us consider this example.
So I have two, three, then one went in for.
I have to reach the last.
Currently, I am present at the first index.
Now this is Valetta.
So there are two possibilities.
I can take a jump of one and I can reach three, or I can take a jump off two and I can reach one.
OK, let us consider both the options.
OK, so if this is the first option, let's say I am taking a jump of one so I will reach three.
So from three what I can do, I can take a jump of three and I can reach for ok, I can take a jump
of three and I can reach for.
So in this case my output will be true.
OK, I have to return a boolean value you can see after the double in value.
So since I am able to reach the last index, I will return to simple.
Now if it will take a jump of two.
This is the second option if you take a bottle now from one that makes them jump, you can take is one.
Now, again, from when the maximum you can take is also one.
OK, so if you will follow the second option also, then also you are able to reach the last Hynix,
OK, so you can either take a jump of one or you can either take a jump of two.
You are able to reach the last or next since you are able to reach the next year.
Also in this case will be through.
Simple.
Now, let us consider this example, I have three, two, one, zero and four, I am standing here at
the first position and I want to reach the last index.
So let's say I'm digging a jump of index three.
Sorry, I'm taking a jump of three.
So if I'm taking a jump of three, I will reach a zero.
So from zero, I cannot take any jump.
So this method is wrong.
I'm not able to reach the last index.
Now, if I take a jump off two, I will reach one, so from one, I can only take a jump of one, so
I will reach a zero.
So again, from zero, we cannot reach the last index.
So this option is also wrong.
Now, if I take a jump of one now from two, I can take a jump of one or I can jump off to if I will
take a jump of two, I will reach zero.
And from zero I cannot go anywhere else.
So this is wrong.
If I take a jump of one, I will reach one and from when I can only take a jump of one.
So this is also wrong because we will reach a zero again.
So in this case, there is no way I can reach the last index.
There's no way to reach the last index, so in this case, my output will be false.
OK, my output will be false.
I have to return a boolean value.
And in this case, I will return false because there is no way for us to reach the last index starting
from the first index.
So how we can solve this question.
So basically the main idea behind solving this question, the main idea behind this question is basically
let us define two indexes, so let us take two times good index.
And the second term is basically bad index.
So what does the meaning of good index so good index means that index from which we can reach the Lastra
index from which we can reach last index.
OK, and what is a bad index.
So bad index is just the opposite of good index.
OK, so this is the index from which we cannot reach Lastra index, so we are defining to dumps good
index and index.
Now let's discuss the main idea behind solving this question.
So if.
You are standing so there is current position.
OK, you are standing at this position, so let's name it current position.
So if current position plus.
NAMS is the name of the ad, OK, so you can see them, says the name of the ad.
So if no, if current operation listen so far, so far is basically the maximum that I can pick.
So if current position bless them, Sophi is greater than or equal to last most good index, then what
is the meaning?
OK, so what we can draw from here, what will be the result.
So the result will be basically the current position is also a good index.
Current position is also a good index.
OK, if you will understand this thing, then the question is solid.
So I'm repeating myself.
You are standing at the current position and if you need the current position, so if current position
plus Nimsoft, OK, current position plus.
So this would be basically this is not a this is basically current position only.
OK.
So you are standing at the current position, if the maximum jump you can take is basically Nimsoft
current position, so if current position plus Nimsoft current position is greater than or close to
the last most or you can say the rightmost.
So if this is good, then close to rightmost the good next.
Then the current position is also a good index, obviously.
OK, just try to think carefully.
I'm repeating myself.
You're standing at the current position.
The maximum jump you can take is basically Nemstov current position, OK?
The maximum you can take is basically Nimsoft current position.
So if this thing if this thing is basically graded then or goes to the rightmost good index.
That means the current position is also good and it's very, very simple now we will use this approach
to solve the question.
OK, we will use this approach to solve this question, let us take an example.
Let's take this example two three one one four.
OK, let us take this example.
So two, then three, then one, then one, then four.
So what is my rightmost?
Good index.
So this is the rightmost.
Good index.
OK, so this is the rightmost good index.
Now start from here.
We will traverse the error in the backward direction.
So you are standing at one, you are standing at this index.
So this is zero one, two, three and four.
So currently the eight most good index is basically four.
You are standing at index three, OK, you're standing at index three, the maximum number you can take.
OK, so current position plus Nimsoft, I saw three is the current position plus nothing so far is basically
one.
So three plus one is basically greater than or equal to four.
That means this is also a good index.
So I will update my last most good index.
So what I will do, I will argue will come here.
Right, good index.
OK, so my ablated are just basically three since we are trading over the area, I will reach here.
So this index is basically two.
So two plus one.
So again, this is basically Gardino close to three.
That means this is also a good index.
So I will update Miyaji.
OK, so now the charges basically do now come here, so the index is basically one and the value is
basically three.
So when close to identical to do.
OK, so this is also true.
So R.G. will come here.
Right here and.
Right.
Good index will come here.
Now I'm standing here, so this is zero zero close to what is our DUI charges, basically one so zero
plus two is getting close to one.
That means this is the r.g OK.
And finally my arrival and OK.
And where is R.G.?
So R.G. is basically at the next to zero.
OK, so basically index zero.
What is an index zero?
Zero is basically a good index.
OK, and Texada is basically a good index.
And what is the meaning of good index.
So good index is that index from where I can reach the last index, since zero is a good index, that
means I will be able to reach the last position.
So I will return to.
So I will return through simple let's take one more example in that case.
So let's take this example.
In this case, I will not be able to reach the last minute.
So three two one zero four.
Three two one zero four.
So in this example, basically, every index is basically good index.
OK, every index is good index.
Now, I am taking this example, three two one zero four three two, one, zero and four.
OK, so this is my good index initially.
So this is basically index.
So zero one, two, three and four.
So this is good.
Index is basically four.
OK, now come here.
So this is an index T, so index three plus zero.
What I'm doing current position plus number of current position.
OK, so triple zero, is it good then or close to four.
No this is not true.
So that means this is a bad index.
OK, now come here.
So this is an index to show two plus one is guerdon or equal to four.
No, this is not true.
So that means this is also about index.
Malcolm here.
So this is basically two sorry, next one, so superannuation is one plus maximum I can take is basically
two.
So one plus two is Tehsil is triggered, then Noriko's to vote no.
So this is also about bad index now comes here.
So this is like zero zero zero plasty.
So is it good then.
Articles to for.
No.
So that means this is also about index.
And finally, finally, I will reach the minus one index.
OK, so then I will stop.
So what is the gold index?
So basically, I have to check for the first index only.
So is the first index a good index?
What about index?
It is a bad index.
So basically the first operation, the point at which I am standing index zero.
So this is basically a bad index.
And what is the meaning of bad?
Bad means?
I will not be able to reach the last index.
OK, I will not be able to reach the last index, so I will return for in this case.
So this is the only good index here.
This is the only good index here.
The index for is the only good index from basically from index four you can reach index for OK, from
index four you can reach index four.
But from index zero you cannot reach index four.
From index one you cannot reach index four from index to you cannot reach index four from index three,
you cannot reach index four.
OK, so all these are bad indexes.
All these are bad indexes.
So I hope you understood the logic.
So basically, they mean the idea behind this caution is basically to understand this thing, OK, if
you're standing at the current position, if you will, and I'm writing again, OK?
I am writing again, so I hope you understood the meaning of the last, the good and the bad index.
OK, so if the current position, if you're standing at the current position, what is the maximum jump
you can take?
The maximum you can take is basically Nemstov current position.
So if this thing is basically greater than or equal to the rightmost, good index, the rightmost,
good index.
Good index is the index from where you can reach the end.
That means the current position, the current index.
That means the current position is also a good index.
OK, so this is the main logic.
So I hope you understood the logic.
Now let's write the code.
So writing code is very, very simple.
This will be like four to five lines of code.
So let us first find out the size.
So this is numbers, not size.
And I'm straight size.
OK, so initially, what is the good index?
So last word, let's call it.
OK, so let's call it good position.
So and minus one is the good, because from the last index, I can reach the index.
OK, so what?
The position is in minus one.
Now we have to wait it over the area to ECLSS and minister.
I get it, then I get close to zero.
A minus, minus, OK, simple.
Now, which condition I have to use, so I will use this condition contemplation, platinum's of granulation.
So in our case, I'm using for lupus or what is the current condition?
Is I.
OK.
So if the current position, bless them, makes them jump, that I can take is basically Nimsoft.
So if this thing.
It's basically guerdon articles to.
They go to perdition.
That means the current operation is also going to position.
OK, so the current position is also good position.
So I will update and equal the position.
Now, finally, what we have to do, I have to check for the next zero.
OK, finally what we have to do, I have to check for the index zero weather index zero is a good politician
or a bad position.
Now check.
So if good position is index zero, if basically index zero is a good position, then you will return
to.
Otherwise, you will return false.
OK, so this is the complete gold.
Now, let's first an hour and then we will submit.
OK, so our goal is working fine now let's meet our goal.
Now, what will we do, time in the space complexity of our solution, so it is very simple.
So the time, complexity of our solution is big often and the space complexities big of one.
OK, so this is the time and this is the space.
OK, so this was a very simple question.
OK, if you do not like the name, you can also change it like last a good index and then you can update
the last good index.
OK.
So we are just reversing from the last operation to the first operation, and the idea is basically
if the index is zero.
If Index zero is a good opposition.
If there is a good portion, that means I will be able to reach the last Olympics.
OK, that is the meaning of good word means the index from which you can you can reach the last Hynix.
So if you have any doubt in this question, you can ask me.
OK, thank you.