Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You have been given an array * 'ARR'* of

From index ‘i’, we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] .

'ARR[i]' represents the maximum distance you can jump from the current index.

If it is not possible to reach the last index, return -1.

```
Consider 0-based indexing.
```

```
Consider the array 1, 2, 3, 4, 5, 6
We can Jump from index 0 to index 1
Then we jump from index 1 to index 2
Then finally make a jump of 3 to reach index N-1
There is also another path where
We can Jump from index 0 to index 1
Then we jump from index 1 to index 3
Then finally make a jump of 2 to reach index N-1
So multiple paths may exist but we need to return the minimum number of jumps in a path to end which here is 3.
```

Detailed explanation

```
5
2 3 1 1 4
```

```
2
```

```
Consider the above figure:
We are initially at index 0, ARR[0] is 2 which represents we can jump a maximum of 2 steps.
We jump 1 index from 0 to 1. At index 1, 'ARR[1]' is 3 which represents we can jump a maximum of 3 steps so we jump 3 indices from 1 to 4 to reach the last index. Hence we return 2.
It can be proved that the end can't be reached in less than 2.
```

```
5
3 2 1 0 1
```

```
-1
```

```
1 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 4
Where ‘ARR[i]’ denotes the ‘i-th’ element of the ‘ARR’.
Time limit: 1 sec.
```