Welcome back.
In the previous video, we discussed that at every index, we will just try to jump to the farthest
reachable index from each reachable index.
Now there are two aspects in this statement.
The first aspect is jump to the farthest reachable index.
And the second aspect in this statement is from each reachable index.
Now let's try to understand these two pieces to thoroughly understand this approach.
And for this let's take an example.
Let's say the array which is given to us is 20132.
And I've also written the indices over here which span from zero till four.
Now we start at index zero.
And the farthest reachable index from this index over here would be zero plus two.
Okay.
That's taking a jump to this index over here.
So from index zero the farthest reachable index is index two.
All right.
Now we move to the next index.
And we see that this index over here first of all is reachable which is the second criteria over here.
Because you can just take one step from this place to reach over here.
So this index over here first of all is reachable.
And once you reach this index over here you cannot take any jump.
You can't move forward.
So the farthest reachable index from this index is one itself okay.
So we have covered these two aspects when we consider this index.
Now let's go ahead and go through the remaining indices so that this becomes very clear.
Now we come to this place over here this index.
First of all we see that this index which is index two is reachable because you can just take two steps
from index zero to reach index two.
So index two first of all is reachable.
And once you reach index two, the farthest reachable index from index two would be index two plus one,
which gives you three.
Okay.
So again we have covered these two aspects.
Now we move to the next index.
So we come over here.
And again we see that this index which is three is reachable because you can take one step from this
place over here.
So this index is reachable.
And once you reach over here you can reach the last index because you can take up to three steps.
And you just need to take one step to reach the last index.
And therefore at this point we can just return true because we have seen that yes, I can reach the
last index of the array which is given to me.
So what we have seen over here is that we just need to iterate through the indices over here in the
array which is given to us.
And we need to keep checking whether that particular index is reachable.
Now if it is not reachable, we would just return false because we would not be able to go further.
And I'll show that to you in one more example.
But if it is reachable, we will also calculate the farthest reachable index from that particular index.
And we'll keep doing that.
And if we see that at some point we are able to reach the last index of the array which is given to
us, then we will just return true.
Now let's take a look at one more interesting example to thoroughly understand this approach.
So let's say this is the array which is given to us.
And the indices span from zero up to nine.
And again we start at index zero.
Now from index zero the maximum reachable index is zero plus two which gives me two okay.
And I proceed to the next index.
Now I see that index one is reachable because I can take one step from index zero, and the maximum
index that I can reach from index one would be one plus three, which is equal to four.
We proceed to the next index.
We see that two is reachable because the maximum reachable index at this point is four.
So anything up to four is reachable okay.
So two is reachable and the maximum that you can reach from index two would be two plus one which is
three.
Again we come to index three three is reachable.
And from three the maximum that you can reach is three plus zero which is three itself.
And four is also reachable.
So we have seen that over here.
So up to four the indices are reachable.
But starting index five the indices are not reachable.
Right.
Because notice all of these values are zero.
So the maximum that is reachable from here will be three itself.
And the maximum index that is reachable from this position over here will be four itself.
So the indices beyond four which are the indices starting at five and going up to nine are not reachable.
And for that reason we are not able to go beyond index four, which means that we are not able to reach
the last index of the array which is given to us, and hence we can just return false.
Okay.
So again these are the two aspects of this algorithm.
We need to jump to the farthest reachable index from each reachable index.
Now, if you see that at some point the index where you reached is not reachable, and that would happen
in this example, once you keep iterating over the indices, you start over here.
And then once you reach over here, you would have reached an index which is not reachable.
And at that point you can just return false.
So this is the first approach which we will use to solve this question.
And notice that this is a greedy algorithm.