# Minimum Number of Jumps to Reach End

##### January 10, 2024

## Problem #

You are given an array `arr`

of positive integers, representing the maximum number of jumps you can make from each index. You start from the first index and must reach the last index. Find the minimum number of jumps required to reach the end of the array.

## Solution #

To solve this problem, we can use dynamic programming (DP). We will create a new DP array `dp`

and initialize it with infinity except for the first element, which is set to 0. Then, we iterate through the array and update each cell of `dp`

by considering the minimum number of jumps required from all previous indices.

### Code: #

```
def minJumps(arr):
n = len(arr)
# If the array has only one element
if n <= 1:
return 0
# If the first element is 0, it's not possible to move forward
if arr[0] == 0:
return -1
jumps = [float('inf')] * n
jumps[0] = 0
# Building the jumps array using dynamic programming
for i in range(1, n):
for j in range(i):
if i <= j + arr[j] and jumps[j] != float('inf'):
jumps[i] = min(jumps[i], jumps[j] + 1)
break
return jumps[-1] if jumps[-1] != float('inf') else -1
# Example usage
arr = [2, 3, 1, 1, 2, 4, 2, 0, 1, 1]
print(minJumps(arr)) # Output will be the minimum number of jumps
```

### Explanation: #

`n`

is the length of the array`arr`

.- We initialize a
`jumps`

array where`jumps[i]`

will eventually store the minimum number of jumps to reach index`i`

. - We iterate through each element of
`arr`

. For each element, we look back at all previous elements and check if that element can jump to the current element. If it can, we update the`jumps[i]`

with the minimum number of jumps needed to reach`i`

. - If the end of the array is reachable,
`jumps[-1]`

will contain the minimum number of jumps; otherwise, it will be`float('inf')`

, and we return`-1`

to indicate it’s not possible to reach the end.

### Time Complexity #

O(n^2), where ’n’ is the length of the array. This is because we are iterating through each index twice (once for updating `minJumps`

and once for updating `dp`

).

### Space Complexity #

O(n) as we create a new DP array of size ’n’ to store the minimum number of jumps for each index.