Welcome back.
Let's now implement the code for solving the jump game question.
And we're given this Numb's array over here.
And let's say n is the length of the array which is given to us.
Okay.
And the approach that we are going to implement over here is by just iterating through the elements
in the Nums array.
And then we'll keep finding the maximum reachable index.
And if at any point we see that the maximum reachable index is the last index or even greater than the
last index, we can just go ahead and return.
True.
But if at any point, as we iterate through the numb's array using, let's say, a variable I, and
let's say at any point I becomes greater than the max reachable index, then we would just return false.
Now again, let me quickly explain that.
But before that let's write this for loop.
So let I equal to zero I less than n I plus plus okay.
So we are using this to iterate through every index in the numb's array.
And if at any point we see that I is greater than the max index that we can reach, and again we would
need a variable for that.
And let's define max index initially to be equal to zero okay.
And if at any point I is greater than max index we can just return false okay.
Now let's quickly understand this.
Now let's say the array which is given to us is something like one two.
And then you have 0000 and then you have four.
Okay.
Now if at any point you reach beyond this index like let's say you reach this index over here, okay,
which has the value 01234 okay.
When you reach I equal to four, you will see that this is a place that you can't even reach, right.
Like for example, from here, if you take two steps, the maximum that you can reach is over here.
But this is beyond that, right?
Therefore, forget the last index.
You won't be able to reach here or anything beyond that.
And that's why over here we will be able to return false.
And again notice that initially max index was set to zero.
And in the first iteration I will take the value zero and zero is not greater than zero.
So this will not execute.
And we proceed okay.
Now what we will do is we will go ahead and keep identifying the maximum reachable index, which would
be the maximum between what is already there at max index and I plus numb's at I.
Okay.
For example, notice in this example, initially max index is equal to zero.
But then when I takes the value zero from here I can take one step.
So therefore max index is the greater value between what's already there which is zero and zero plus
one which is one.
Right.
And in that case one is greater.
So therefore max index changes to one which is this index over here.
And that's the maximum reachable index when we are over here.
Similarly when we come over here the maximum reachable index becomes equal to three okay.
So we keep updating the maximum reachable index over here.
And at any point if we see that max index is greater than or equal to n minus one, then we can just
return true because we are definitely able to reach the last index okay.
And that's it.
So this should take care of it.
Now after you're out of the for loop you can just return false.
And again you will see that you can in fact just avoid this line as well because we are already taking
care of the scenario where we want to return false over here.
Now let's go ahead and run this code and see if it's passing all the test cases.
And after that, let's also run it once more without this line of code, just to demonstrate that you
actually don't need that.
And again, I've seen I've made a typo over here.
So let me quickly correct that.
All right.
So let's run it.
And you can see that it's working.
It's passing all the test cases.
Now let's remove this line and run it once more.
And you can see that it's still working okay.
So this is how we can solve Jump game one.
And notice that we have used a greedy algorithm to achieve this.