1
00:00:00,110 --> 00:00:01,040
Welcome back.

2
00:00:01,040 --> 00:00:05,030
In the previous video we discussed the first greedy approach.

3
00:00:05,030 --> 00:00:08,420
Now over here, let's take a look at one more greedy approach okay.

4
00:00:08,420 --> 00:00:10,970
And for this let's again take an example.

5
00:00:10,970 --> 00:00:15,290
Let's say this is the array which is given to us which is 20132.

6
00:00:15,290 --> 00:00:17,750
And the indices span from 0 to 4.

7
00:00:17,750 --> 00:00:22,100
Now in this approach we will start from the last index.

8
00:00:22,100 --> 00:00:25,070
And then we'll keep moving the goalpost okay.

9
00:00:25,070 --> 00:00:28,970
And with goalpost I mean the position that we want to reach.

10
00:00:28,970 --> 00:00:30,830
So we are starting at index four.

11
00:00:30,830 --> 00:00:34,550
And at this point the goalpost is index four.

12
00:00:34,550 --> 00:00:38,480
Because the question says that we want to be able to reach over here.

13
00:00:38,480 --> 00:00:42,320
Now what we will do is we will come to the previous index.

14
00:00:42,320 --> 00:00:49,250
So we come to index three and we will check whether it's possible to reach index four from index three.

15
00:00:49,250 --> 00:00:53,540
And we see that it's possible because we have a value of three over here.

16
00:00:53,540 --> 00:00:56,510
So we can make jumps up to length three.

17
00:00:56,510 --> 00:01:00,800
And we just need to make a jump of length one to reach from 3 to 4.

18
00:01:00,800 --> 00:01:05,630
So we see that it's possible to reach index four from index three.

19
00:01:05,630 --> 00:01:11,360
And because it's possible we will move the goalpost from index four to index three.

20
00:01:11,360 --> 00:01:12,710
So let's do that over here.

21
00:01:12,710 --> 00:01:15,680
So the goalpost at this point is index three.

22
00:01:15,710 --> 00:01:19,490
Now again we proceed to the previous index which is index two.

23
00:01:19,490 --> 00:01:23,480
And we're going to check whether we can reach from index two to index three.

24
00:01:23,480 --> 00:01:27,470
And we see that it's possible because the value over here is one okay.

25
00:01:27,470 --> 00:01:31,220
And we can make a jump of one to reach from index 2 to 3.

26
00:01:31,220 --> 00:01:32,600
So this is possible.

27
00:01:32,600 --> 00:01:38,210
And therefore we again move the goalpost from index three to index two okay.

28
00:01:38,210 --> 00:01:40,700
So the goalpost at this point is index two.

29
00:01:40,700 --> 00:01:42,620
And we move to the previous index.

30
00:01:42,620 --> 00:01:47,510
We come over here and we're going to check whether we can reach index two from index one.

31
00:01:47,510 --> 00:01:51,890
And we see that it's not possible because the value over here is zero.

32
00:01:51,890 --> 00:01:54,920
So we are not able to move forward from this index okay.

33
00:01:54,920 --> 00:01:57,410
So we do not change the goalpost.

34
00:01:57,410 --> 00:01:59,900
The goalpost remains at index two.

35
00:01:59,900 --> 00:02:01,910
And we go to the previous index.

36
00:02:01,910 --> 00:02:04,430
So we come over here okay.

37
00:02:04,430 --> 00:02:07,610
So we come over here and we are at index zero.

38
00:02:07,610 --> 00:02:14,930
And we see that from index zero I am able to reach the goalpost which is index two because the value

39
00:02:14,930 --> 00:02:15,740
over here is two.

40
00:02:15,740 --> 00:02:20,300
And I can just make a jump of length two to reach index two from index zero.

41
00:02:20,300 --> 00:02:25,610
So it's possible to reach the goalpost which is index two from index zero.

42
00:02:25,610 --> 00:02:31,280
And for that reason we'll change the goalpost and we will move it to this position over here which is

43
00:02:31,280 --> 00:02:32,720
index zero okay.

44
00:02:32,720 --> 00:02:39,020
And finally we will just check whether the goalpost is equal to zero.

45
00:02:39,020 --> 00:02:47,720
Because if the goalpost is equal to zero, it implies that we can reach index four from index zero.

46
00:02:47,720 --> 00:02:52,880
So if the goalpost at the end is equal to zero, we will just return true.

47
00:02:52,880 --> 00:02:56,480
And if this is not the case, then we will return false.

48
00:02:56,480 --> 00:03:00,260
Like for example, think of the scenario where you have zero over here.

49
00:03:00,260 --> 00:03:05,840
So if you have zero over here and when we come to this index, we see that we are not able to reach

50
00:03:05,840 --> 00:03:08,930
the goal post, which at that point is two from zero.

51
00:03:08,930 --> 00:03:09,260
Right.

52
00:03:09,260 --> 00:03:13,790
And therefore we would not move the goalpost and the goalpost would remain at index two.

53
00:03:13,790 --> 00:03:18,560
And finally, when we check whether the goalpost is equal to zero, we see that it's not the case.

54
00:03:18,560 --> 00:03:18,950
Okay.

55
00:03:18,950 --> 00:03:20,360
And then we would return false.

56
00:03:20,360 --> 00:03:20,750
Okay.

57
00:03:20,750 --> 00:03:25,640
I'm just talking about the scenario where the input array is this over here okay.

58
00:03:25,640 --> 00:03:27,440
So in this case we would return false.

59
00:03:27,440 --> 00:03:31,850
So this is the second approach which we can use to solve this question.

60
00:03:31,850 --> 00:03:35,750
And again notice this also is a greedy algorithm.