# Minimum jumps to reach end of array

Given an array of integers, ** find minimum jumps to reach end of the array**. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

## Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s

Of all the jumps possible from *minJumps(start, end)*`start`, let’s say we go to index `k`, then what how does problem reduces? Well, now we have to find minimum number of jumps from `k` to `end`. How to decide on `k` now? We try all k values from start+1 to start + a[i].

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

Now, we have clear recursion relationship, what should be the base case? When `k + A[k]`

> end, or `k == end`

, we should return 1 as there would be only one jump required from k to end now.

package com.company; /** * Created by sangar on 10.10.18. */ public class MinimumJumps { public int minimumNumberOfJump(int[] a, int start, int end){ //If start == end, we reached the end, return 0. if(start == end) return 0; //if current element is 0, you cannot jump to end at all if(a[start] == 0) return Integer.MAX_VALUE; int minimumJumps = Integer.MAX_VALUE; for(int k=start+1; k<=start+a[start] && k<=end; k++){ /* For each K from start+1 to end, find the minimum jumps. */ int jumps = minimumNumberOfJump(a,k,end); if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){ minimumJumps = jumps + 1; } } return minimumJumps; } }

**Test cases for above function**

package test; import com.company.MinimumJumps; import org.junit.jupiter.api.Test; import static org.junit.Assert.assertEquals; /** * Created by sangar on 23.9.18. */ public class MinimumJumpTest { MinimumJumps tester = new MinimumJumps(); @Test public void baseTest() { int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}; assertEquals(3, tester.minimumNumberOfJump(a,0, a.length-1)); } @Test public void arrayContainsZeroTest() { int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9}; assertEquals(Integer.MAX_VALUE, tester.minimumNumberOfJump(a,0, a.length-1)); } @Test public void nullArrayTest() { assertEquals(0, tester.minimumNumberOfJump(null,0, 0)); } @Test public void arrayWithTwoElementsTest() { int[] a = {1, 0}; assertEquals(1, tester.minimumNumberOfJump(a,0, a.length-1)); } }

Let’s see execution trace of above function for an input.

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.

Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. `Jump[i]`

represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each `i`, from j = 0 to i-1 and check if j+a[j] <= i, if yes, update `jump[i] = min (jump[i], jump[j]+1)`

.

### Minimum number of jumps: dynamic programming approach

package com.company; /** * Created by sangar on 10.10.18. */ public class MinimumJumps { public int minimumNumberOfJumpDP(int[] a){ if(a == null || a.length == 0) return 0; if(a[0] == 0) return Integer.MAX_VALUE; int[] jump = new int[a.length]; //no jumps required for first element jump[0] = 0; for(int i=1; i<a.length;i++){ jump[i] = Integer.MAX_VALUE; for(int j=0; j<i; j++){ if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){ jump[i] = Integer.min(jump[i], 1 + jump[j]); } } } return jump[a.length-1]; } }

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is `O(n`

with space complexity of ^{2})`O(n)`

If you are interested to solve this problem in `O(n)`

time, please visit stack overflow discussion

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at communications@algorithmsandme.com