1
00:00:00,600 --> 00:00:01,710
Welcome back.

2
00:00:01,710 --> 00:00:08,760
In the previous video, we discussed that at every index, we will just try to jump to the farthest

3
00:00:08,760 --> 00:00:12,090
reachable index from each reachable index.

4
00:00:12,120 --> 00:00:14,700
Now there are two aspects in this statement.

5
00:00:14,700 --> 00:00:19,140
The first aspect is jump to the farthest reachable index.

6
00:00:19,140 --> 00:00:24,090
And the second aspect in this statement is from each reachable index.

7
00:00:24,090 --> 00:00:28,980
Now let's try to understand these two pieces to thoroughly understand this approach.

8
00:00:28,980 --> 00:00:31,050
And for this let's take an example.

9
00:00:31,050 --> 00:00:35,040
Let's say the array which is given to us is 20132.

10
00:00:35,040 --> 00:00:40,230
And I've also written the indices over here which span from zero till four.

11
00:00:40,230 --> 00:00:42,810
Now we start at index zero.

12
00:00:42,810 --> 00:00:48,840
And the farthest reachable index from this index over here would be zero plus two.

13
00:00:48,870 --> 00:00:49,290
Okay.

14
00:00:49,290 --> 00:00:51,810
That's taking a jump to this index over here.

15
00:00:51,810 --> 00:00:57,630
So from index zero the farthest reachable index is index two.

16
00:00:58,050 --> 00:00:58,530
All right.

17
00:00:58,560 --> 00:01:01,170
Now we move to the next index.

18
00:01:01,170 --> 00:01:08,490
And we see that this index over here first of all is reachable which is the second criteria over here.

19
00:01:08,490 --> 00:01:12,630
Because you can just take one step from this place to reach over here.

20
00:01:12,630 --> 00:01:16,260
So this index over here first of all is reachable.

21
00:01:16,260 --> 00:01:20,910
And once you reach this index over here you cannot take any jump.

22
00:01:20,910 --> 00:01:22,170
You can't move forward.

23
00:01:22,170 --> 00:01:27,330
So the farthest reachable index from this index is one itself okay.

24
00:01:27,330 --> 00:01:31,290
So we have covered these two aspects when we consider this index.

25
00:01:31,290 --> 00:01:35,910
Now let's go ahead and go through the remaining indices so that this becomes very clear.

26
00:01:35,910 --> 00:01:38,490
Now we come to this place over here this index.

27
00:01:38,490 --> 00:01:45,540
First of all we see that this index which is index two is reachable because you can just take two steps

28
00:01:45,540 --> 00:01:48,210
from index zero to reach index two.

29
00:01:48,210 --> 00:01:51,300
So index two first of all is reachable.

30
00:01:51,300 --> 00:01:59,550
And once you reach index two, the farthest reachable index from index two would be index two plus one,

31
00:01:59,550 --> 00:02:00,900
which gives you three.

32
00:02:00,900 --> 00:02:01,320
Okay.

33
00:02:01,320 --> 00:02:03,750
So again we have covered these two aspects.

34
00:02:03,750 --> 00:02:06,000
Now we move to the next index.

35
00:02:06,000 --> 00:02:07,290
So we come over here.

36
00:02:07,290 --> 00:02:14,070
And again we see that this index which is three is reachable because you can take one step from this

37
00:02:14,070 --> 00:02:14,820
place over here.

38
00:02:14,820 --> 00:02:17,130
So this index is reachable.

39
00:02:17,130 --> 00:02:23,850
And once you reach over here you can reach the last index because you can take up to three steps.

40
00:02:23,850 --> 00:02:27,480
And you just need to take one step to reach the last index.

41
00:02:27,480 --> 00:02:34,620
And therefore at this point we can just return true because we have seen that yes, I can reach the

42
00:02:34,620 --> 00:02:37,470
last index of the array which is given to me.

43
00:02:37,470 --> 00:02:42,960
So what we have seen over here is that we just need to iterate through the indices over here in the

44
00:02:42,960 --> 00:02:44,190
array which is given to us.

45
00:02:44,190 --> 00:02:48,270
And we need to keep checking whether that particular index is reachable.

46
00:02:48,270 --> 00:02:54,000
Now if it is not reachable, we would just return false because we would not be able to go further.

47
00:02:54,000 --> 00:02:57,330
And I'll show that to you in one more example.

48
00:02:57,330 --> 00:03:04,020
But if it is reachable, we will also calculate the farthest reachable index from that particular index.

49
00:03:04,020 --> 00:03:05,490
And we'll keep doing that.

50
00:03:05,490 --> 00:03:10,860
And if we see that at some point we are able to reach the last index of the array which is given to

51
00:03:10,860 --> 00:03:13,410
us, then we will just return true.

52
00:03:13,440 --> 00:03:18,840
Now let's take a look at one more interesting example to thoroughly understand this approach.

53
00:03:18,840 --> 00:03:21,360
So let's say this is the array which is given to us.

54
00:03:21,360 --> 00:03:24,990
And the indices span from zero up to nine.

55
00:03:24,990 --> 00:03:27,360
And again we start at index zero.

56
00:03:27,360 --> 00:03:34,710
Now from index zero the maximum reachable index is zero plus two which gives me two okay.

57
00:03:35,220 --> 00:03:37,710
And I proceed to the next index.

58
00:03:37,710 --> 00:03:44,280
Now I see that index one is reachable because I can take one step from index zero, and the maximum

59
00:03:44,280 --> 00:03:49,680
index that I can reach from index one would be one plus three, which is equal to four.

60
00:03:49,680 --> 00:03:51,420
We proceed to the next index.

61
00:03:51,420 --> 00:03:57,120
We see that two is reachable because the maximum reachable index at this point is four.

62
00:03:57,120 --> 00:03:59,760
So anything up to four is reachable okay.

63
00:03:59,760 --> 00:04:05,910
So two is reachable and the maximum that you can reach from index two would be two plus one which is

64
00:04:05,910 --> 00:04:06,420
three.

65
00:04:06,450 --> 00:04:09,900
Again we come to index three three is reachable.

66
00:04:09,900 --> 00:04:14,520
And from three the maximum that you can reach is three plus zero which is three itself.

67
00:04:14,520 --> 00:04:16,590
And four is also reachable.

68
00:04:16,590 --> 00:04:18,030
So we have seen that over here.

69
00:04:18,030 --> 00:04:21,090
So up to four the indices are reachable.

70
00:04:21,090 --> 00:04:26,040
But starting index five the indices are not reachable.

71
00:04:26,040 --> 00:04:26,310
Right.

72
00:04:26,310 --> 00:04:28,620
Because notice all of these values are zero.

73
00:04:28,620 --> 00:04:31,740
So the maximum that is reachable from here will be three itself.

74
00:04:31,740 --> 00:04:36,180
And the maximum index that is reachable from this position over here will be four itself.

75
00:04:36,180 --> 00:04:43,860
So the indices beyond four which are the indices starting at five and going up to nine are not reachable.

76
00:04:43,860 --> 00:04:50,790
And for that reason we are not able to go beyond index four, which means that we are not able to reach

77
00:04:50,790 --> 00:04:56,340
the last index of the array which is given to us, and hence we can just return false.

78
00:04:56,340 --> 00:04:56,730
Okay.

79
00:04:56,730 --> 00:05:00,120
So again these are the two aspects of this algorithm.

80
00:05:00,240 --> 00:05:05,670
We need to jump to the farthest reachable index from each reachable index.

81
00:05:05,700 --> 00:05:12,060
Now, if you see that at some point the index where you reached is not reachable, and that would happen

82
00:05:12,060 --> 00:05:16,200
in this example, once you keep iterating over the indices, you start over here.

83
00:05:16,200 --> 00:05:20,640
And then once you reach over here, you would have reached an index which is not reachable.

84
00:05:20,640 --> 00:05:23,580
And at that point you can just return false.

85
00:05:23,580 --> 00:05:27,450
So this is the first approach which we will use to solve this question.

86
00:05:27,450 --> 00:05:29,970
And notice that this is a greedy algorithm.