## Minimum Jumps To Reach End of an Array

Given an array of non-negative integers, **A**, of length **N**. You are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position.

Return the minimum number of jumps required to reach the last index.

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

**Examples:**

**Input: **arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]**Output: **3**Explanation: **Provided in the above image

**Input: ** arr[] = [2, 3, 1, 1, 4]**Output:** 2**Explanation:** Travel from 2 -> 3 -> end.

## Approach 1: Bruteforce(Recursive)

A simple approach to solve this problem is to start from the first element of the array and recursively travel to all elements that are reachable from that element. Similarly, recursively travel to all other elements and find the minimum jumps to reach the end of the array.

**Algorithm:**

- Create a recursive function that determines the minimum jumps required to reach the end of the array.
- Start from the first element of the array and recurse for each step till current step > 0.
- Minimise the value for each iteration.
- Return the minimum jumps.

### C++ Implementation

int decideJump(int nums[], int n, int currPos){ if(currPos >= n-1){ return 0; } int minJump = INT_MAX; int maxSteps = nums[currPos] while(maxSteps > 0){ minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps)) maxSteps = maxSteps - 1; } return minJump } int jump(int nums[], int n) { return decideJump(nums, n, 0); }

### Java Implementation

int decideJump(int[] nums, int n, int currPos){ if(currPos >= n-1){ return 0 } int minJump = INT_MAX int maxSteps = nums[currPos] while(maxSteps > 0){ minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps)) maxSteps = maxSteps - 1 } return minJump } int jump(int[] nums, int n) { return decideJump(nums, n, 0) }

### Python Implementation

def decideJump(nums, n, currPos): if currPos >= n-1: return 0 minJump = 9999999999999 maxSteps = nums[currPos] whilemaxSteps > 0 : minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps)) maxSteps = maxSteps - 1 return minJump def jump(nums, n): return decideJump(nums, n, 0)

**Time Complexity:** O(N^N), where N is the total elements in the array.**Space Complexity:** O(1), since no extra space is used.

## Approach 2: Dynamic Programming

In the previous approach, if you clearly observe the recursion tree, it can be clearly seen that many of the subproblems are calculated more than once, which in turn takes more time as well as space. Therefore, we can store the answer to such overlapping subproblems in a table and get the answer to this problem in O(1) using a **dynamic programming** approach.

**Algorithm:**

- Create a
**dp[]**array of size**N**, where**N**is the size of the given array. - Initialise all the elements of the array to
**INT_MAX**. - Initialise
**dp[0] = 0**, since, we are standing at the first index and we need no jumps to reach the first element. - The recursive structure would be:
**dp[i] = 1 + min(dp[i], 1 + min( dp[i+1], dp[i+2],. . . dp[i + dp[i] + 1]))** - Iterate a loop from 0 till
**N – 1**.**i + 1**till**min(i + arr[i] + 1, n)**and find the minimum of**jumps[i]**and**i + jumps[i]**. - After iterations, return the value of
**dp[N – 1]**

### C++ Code For DP Method

int minJump(int num[], int n){ int dp[n] = {INT_MAX} dp[0] = 0 for(i = 0 to i < n){ for(j = i+1 to j < min(i+num[i]+1, n)) { dp[j] = min(dp[j], 1 + dp[i]) } } return dp[n-1] }

### Java Code For DP Method

int minJump(int[] num, int n){ int[n] dp = {INT_MAX} dp[0] = 0 for(i = 0 to i < n){ for(j = i+1 to j < min(i+num[i]+1, n)) { dp[j] = min(dp[j], 1 + dp[i]) } } return dp[n-1] }

### Python Code For DP Method

def minJump(num, n){ dp = [n] * (99999999) dp[0] = 0 For i in range(n): For j in range(i+1, min(i+num[i]+1, n)): dp[j] = min(dp[j], 1 + dp[i]) return dp[n-1]

**Time Complexity:** O(N^ 2), where N is the total elements in the array.**Space Complexity:** O(N), since **dp[]** array is used.

## Approach 3: Greedy Approach

In the previous approach, it was observed that if we are at position **i**, the maximum one can jump is **(i, i + nums[i])**.

In the below example, only can jump in three different positions from the given index **i**.

**Algorithm:**

- Consider three variables,
**jumps**, which stores the number of jumps,**end**, which denotes the end of the array and**farthest**denoting the farthest one can jump and initialise them to 0. - Traverse over the given array and perform the following operation:
**farthest = i + nums[i]**- If
**end**is reached, then**ith**jump is finished, therefore update**end = farthest**.

- Return total jumps.

### C++ Code For Greedy Approach

int minJump(int nums[], int n) { int jumps = 0, currentJumpEnd = 0, farthest = 0; for (int i = 0; i < n - 1; i++) { farthest = max(farthest, i + nums[i]); if (i == currentJumpEnd) { jumps++; currentJumpEnd = farthest; } } return jumps; }

### Java Code For Greedy Approach

public int minJump(int[] nums) { int jumps = 0, currentJumpEnd = 0, farthest = 0; for (int i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == currentJumpEnd) { jumps++; currentJumpEnd = farthest; } } return jumps; }

### Python Code For Greedy Approach

def minJump(nums): jumps = 0 current_jump_end = 0 farthest = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == current_jump_end: jumps += 1 current_jump_end = farthest return jumps

**Time Complexity:** O(N), where N is the total elements in the array.**Space Complexity:** O(1), since **dp[]** array is used.

## Practice Question

## FAQ

**What is the most efficient approach to solve this problem?**The greedy approach is the most efficient approach since it takes, O(N) time and O(1) space,

**What is the recurrence relation of the dynamic programming approach?**The recurrence relation of the dynamic programming approach is as follows –

dp[i] = 1 + min(dp[i], 1 + min( dp[i+1], dp[i+2],. . . dp[i + dp[i] + 1]))