1
00:00:00,140 --> 00:00:02,030
Hey there and welcome back.

2
00:00:02,060 --> 00:00:08,270
Let's get started with another interesting coding interview question, which is the jump game question.

3
00:00:08,270 --> 00:00:12,110
The question reads you are given an integer array Numb's.

4
00:00:12,110 --> 00:00:19,400
You are initially positioned at the array's first index, and each element in the array represents your

5
00:00:19,400 --> 00:00:22,280
maximum jump length at that position.

6
00:00:22,280 --> 00:00:27,410
Return true if you can reach the last index or false otherwise.

7
00:00:27,410 --> 00:00:31,370
So the question is pretty straightforward, and we're given two examples.

8
00:00:31,370 --> 00:00:37,670
In the first example, the array which is given to us is 1341121.

9
00:00:37,670 --> 00:00:44,030
And it's mentioned that initially we are over here and we need to check whether we can reach the last

10
00:00:44,030 --> 00:00:45,470
index of the given array.

11
00:00:45,470 --> 00:00:51,800
And every value is the maximum jump length that you can take from that particular index.

12
00:00:51,800 --> 00:00:57,260
Now, if this is the array which is given to you, and we start from this place over here, you could

13
00:00:57,260 --> 00:01:03,560
make one jump and reach over here and from here you could reach over here by jumping three positions.

14
00:01:03,560 --> 00:01:05,390
And then you can come over here.

15
00:01:05,390 --> 00:01:07,790
And from here you can come over here.

16
00:01:07,790 --> 00:01:13,730
And again, remember, the value at every index just represents the maximum jump length.

17
00:01:13,730 --> 00:01:18,530
So for example from here the maximum that you can jump is two indices.

18
00:01:18,530 --> 00:01:20,990
But again one is less than two.

19
00:01:21,020 --> 00:01:23,360
So you can jump to this position as well.

20
00:01:23,360 --> 00:01:28,010
So that's why if this is the input array the expected output is true.

21
00:01:28,010 --> 00:01:30,050
Now we are given one more example.

22
00:01:30,050 --> 00:01:37,850
So if the input array is 134211011, the expected output is false.

23
00:01:37,850 --> 00:01:39,380
Now why is that the case.

24
00:01:39,380 --> 00:01:40,880
Let's try to understand that.

25
00:01:40,880 --> 00:01:43,190
So we again starting at this index.

26
00:01:43,190 --> 00:01:46,970
And we could take a jump of length one and reach over here.

27
00:01:46,970 --> 00:01:50,660
And from here let's say we are taking a jump of length three.

28
00:01:50,690 --> 00:01:51,860
We reach over here.

29
00:01:51,860 --> 00:01:55,040
And from here I can take a jump of length one.

30
00:01:55,040 --> 00:02:00,230
I reach over here, and from here again I take a jump of length one and I reach over here.

31
00:02:00,230 --> 00:02:03,950
But from this place over here I cannot move forward.

32
00:02:03,950 --> 00:02:04,310
Right.

33
00:02:04,310 --> 00:02:07,460
And that means I can't reach the last index.

34
00:02:07,460 --> 00:02:13,610
Now, another path that I could try is maybe initially, I take a jump from here to here, and then

35
00:02:13,610 --> 00:02:19,430
from here I take a jump to this position over here because again, remember three just represents the

36
00:02:19,430 --> 00:02:20,840
maximum jump length.

37
00:02:20,840 --> 00:02:23,510
And a jump length of one is less than three.

38
00:02:23,510 --> 00:02:25,730
So I can reach over here from here.

39
00:02:25,730 --> 00:02:30,080
And once I'm over here let's say I take a jump of length four.

40
00:02:30,080 --> 00:02:36,140
And again notice I reach over here and after I reach this position I cannot move forward.

41
00:02:36,140 --> 00:02:42,230
So whatever combination you try, you will see that you will finally reach over here and then you're

42
00:02:42,230 --> 00:02:43,550
not able to move forward.

43
00:02:43,550 --> 00:02:48,290
And for that reason, if this is the input array, the expected output is false.

44
00:02:48,290 --> 00:02:50,240
So this is the question at hand.

45
00:02:50,240 --> 00:02:55,940
Now in the next video let's discuss what approach we can take to solve this question.