1
00:00:00,170 --> 00:00:01,130
Welcome back.

2
00:00:01,130 --> 00:00:05,000
Let's now implement the code for solving the jump game question.

3
00:00:05,000 --> 00:00:07,430
And we're given this Numb's array over here.

4
00:00:07,430 --> 00:00:11,540
And let's say n is the length of the array which is given to us.

5
00:00:12,140 --> 00:00:12,710
Okay.

6
00:00:12,710 --> 00:00:17,960
And the approach that we are going to implement over here is by just iterating through the elements

7
00:00:17,960 --> 00:00:19,130
in the Nums array.

8
00:00:19,130 --> 00:00:22,700
And then we'll keep finding the maximum reachable index.

9
00:00:22,700 --> 00:00:29,300
And if at any point we see that the maximum reachable index is the last index or even greater than the

10
00:00:29,300 --> 00:00:31,580
last index, we can just go ahead and return.

11
00:00:31,580 --> 00:00:31,910
True.

12
00:00:31,910 --> 00:00:37,370
But if at any point, as we iterate through the numb's array using, let's say, a variable I, and

13
00:00:37,370 --> 00:00:44,810
let's say at any point I becomes greater than the max reachable index, then we would just return false.

14
00:00:44,840 --> 00:00:46,640
Now again, let me quickly explain that.

15
00:00:46,640 --> 00:00:48,770
But before that let's write this for loop.

16
00:00:48,770 --> 00:00:52,580
So let I equal to zero I less than n I plus plus okay.

17
00:00:52,580 --> 00:00:56,390
So we are using this to iterate through every index in the numb's array.

18
00:00:56,390 --> 00:01:02,840
And if at any point we see that I is greater than the max index that we can reach, and again we would

19
00:01:02,840 --> 00:01:03,920
need a variable for that.

20
00:01:03,920 --> 00:01:08,180
And let's define max index initially to be equal to zero okay.

21
00:01:08,180 --> 00:01:14,870
And if at any point I is greater than max index we can just return false okay.

22
00:01:14,870 --> 00:01:16,490
Now let's quickly understand this.

23
00:01:16,490 --> 00:01:20,390
Now let's say the array which is given to us is something like one two.

24
00:01:20,390 --> 00:01:24,500
And then you have 0000 and then you have four.

25
00:01:24,500 --> 00:01:24,920
Okay.

26
00:01:24,920 --> 00:01:30,650
Now if at any point you reach beyond this index like let's say you reach this index over here, okay,

27
00:01:30,650 --> 00:01:33,440
which has the value 01234 okay.

28
00:01:33,440 --> 00:01:40,640
When you reach I equal to four, you will see that this is a place that you can't even reach, right.

29
00:01:40,640 --> 00:01:45,320
Like for example, from here, if you take two steps, the maximum that you can reach is over here.

30
00:01:45,320 --> 00:01:47,180
But this is beyond that, right?

31
00:01:47,180 --> 00:01:49,610
Therefore, forget the last index.

32
00:01:49,610 --> 00:01:52,490
You won't be able to reach here or anything beyond that.

33
00:01:52,490 --> 00:01:55,430
And that's why over here we will be able to return false.

34
00:01:55,430 --> 00:01:58,730
And again notice that initially max index was set to zero.

35
00:01:58,730 --> 00:02:04,040
And in the first iteration I will take the value zero and zero is not greater than zero.

36
00:02:04,040 --> 00:02:05,570
So this will not execute.

37
00:02:05,570 --> 00:02:07,040
And we proceed okay.

38
00:02:07,040 --> 00:02:13,430
Now what we will do is we will go ahead and keep identifying the maximum reachable index, which would

39
00:02:13,430 --> 00:02:21,830
be the maximum between what is already there at max index and I plus numb's at I.

40
00:02:22,640 --> 00:02:23,090
Okay.

41
00:02:23,090 --> 00:02:27,680
For example, notice in this example, initially max index is equal to zero.

42
00:02:27,680 --> 00:02:31,940
But then when I takes the value zero from here I can take one step.

43
00:02:31,940 --> 00:02:38,600
So therefore max index is the greater value between what's already there which is zero and zero plus

44
00:02:38,600 --> 00:02:39,560
one which is one.

45
00:02:39,560 --> 00:02:39,920
Right.

46
00:02:39,920 --> 00:02:41,570
And in that case one is greater.

47
00:02:41,570 --> 00:02:45,410
So therefore max index changes to one which is this index over here.

48
00:02:45,410 --> 00:02:48,350
And that's the maximum reachable index when we are over here.

49
00:02:48,350 --> 00:02:54,110
Similarly when we come over here the maximum reachable index becomes equal to three okay.

50
00:02:54,110 --> 00:02:57,320
So we keep updating the maximum reachable index over here.

51
00:02:57,320 --> 00:03:05,540
And at any point if we see that max index is greater than or equal to n minus one, then we can just

52
00:03:05,540 --> 00:03:10,220
return true because we are definitely able to reach the last index okay.

53
00:03:10,220 --> 00:03:10,910
And that's it.

54
00:03:10,910 --> 00:03:12,380
So this should take care of it.

55
00:03:12,380 --> 00:03:16,130
Now after you're out of the for loop you can just return false.

56
00:03:16,130 --> 00:03:21,020
And again you will see that you can in fact just avoid this line as well because we are already taking

57
00:03:21,020 --> 00:03:24,320
care of the scenario where we want to return false over here.

58
00:03:24,320 --> 00:03:28,070
Now let's go ahead and run this code and see if it's passing all the test cases.

59
00:03:28,070 --> 00:03:33,590
And after that, let's also run it once more without this line of code, just to demonstrate that you

60
00:03:33,590 --> 00:03:35,210
actually don't need that.

61
00:03:35,210 --> 00:03:37,310
And again, I've seen I've made a typo over here.

62
00:03:37,310 --> 00:03:38,900
So let me quickly correct that.

63
00:03:38,900 --> 00:03:39,470
All right.

64
00:03:39,470 --> 00:03:40,760
So let's run it.

65
00:03:41,570 --> 00:03:43,190
And you can see that it's working.

66
00:03:43,190 --> 00:03:44,960
It's passing all the test cases.

67
00:03:44,960 --> 00:03:47,990
Now let's remove this line and run it once more.

68
00:03:49,190 --> 00:03:51,980
And you can see that it's still working okay.

69
00:03:51,980 --> 00:03:55,160
So this is how we can solve Jump game one.

70
00:03:55,160 --> 00:03:58,820
And notice that we have used a greedy algorithm to achieve this.