Welcome back.
In the previous video we discussed the first greedy approach.
Now over here, let's take a look at one more greedy approach okay.
And for this let's again take an example.
Let's say this is the array which is given to us which is 20132.
And the indices span from 0 to 4.
Now in this approach we will start from the last index.
And then we'll keep moving the goalpost okay.
And with goalpost I mean the position that we want to reach.
So we are starting at index four.
And at this point the goalpost is index four.
Because the question says that we want to be able to reach over here.
Now what we will do is we will come to the previous index.
So we come to index three and we will check whether it's possible to reach index four from index three.
And we see that it's possible because we have a value of three over here.
So we can make jumps up to length three.
And we just need to make a jump of length one to reach from 3 to 4.
So we see that it's possible to reach index four from index three.
And because it's possible we will move the goalpost from index four to index three.
So let's do that over here.
So the goalpost at this point is index three.
Now again we proceed to the previous index which is index two.
And we're going to check whether we can reach from index two to index three.
And we see that it's possible because the value over here is one okay.
And we can make a jump of one to reach from index 2 to 3.
So this is possible.
And therefore we again move the goalpost from index three to index two okay.
So the goalpost at this point is index two.
And we move to the previous index.
We come over here and we're going to check whether we can reach index two from index one.
And we see that it's not possible because the value over here is zero.
So we are not able to move forward from this index okay.
So we do not change the goalpost.
The goalpost remains at index two.
And we go to the previous index.
So we come over here okay.
So we come over here and we are at index zero.
And we see that from index zero I am able to reach the goalpost which is index two because the value
over here is two.
And I can just make a jump of length two to reach index two from index zero.
So it's possible to reach the goalpost which is index two from index zero.
And for that reason we'll change the goalpost and we will move it to this position over here which is
index zero okay.
And finally we will just check whether the goalpost is equal to zero.
Because if the goalpost is equal to zero, it implies that we can reach index four from index zero.
So if the goalpost at the end is equal to zero, we will just return true.
And if this is not the case, then we will return false.
Like for example, think of the scenario where you have zero over here.
So if you have zero over here and when we come to this index, we see that we are not able to reach
the goal post, which at that point is two from zero.
Right.
And therefore we would not move the goalpost and the goalpost would remain at index two.
And finally, when we check whether the goalpost is equal to zero, we see that it's not the case.
Okay.
And then we would return false.
Okay.
I'm just talking about the scenario where the input array is this over here okay.
So in this case we would return false.
So this is the second approach which we can use to solve this question.
And again notice this also is a greedy algorithm.