**Question:** Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps.

**Example:**

Given array A = {2,3,1,1,4}

Possible ways to reach the end (index list)

- 0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
- 0,1,4 (jump 1 to index 1, and then jump 3 to index 4)

**Answer:**This problem is a classic example of Dynamic Programming. Though we can solve this by brute-force but complexity in that case will be horrendous. If you remember LIS problem or my first post on dynamic programming then we can solve this by using same process.

As soon as we traverse the array, we should find the minimum number of jumps for reaching that position (index) and update our result array. Once we reach at the end, we have the optimum solution at last index in result array.

**How to find optimum number of jump for every position (index)?**

For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.

For (N+1)

^{th}element, initialize result[N+1] as infinite. Then we should go through a loop from 0…N, and at every index (i), we should see if we are able to jump to (N+1) from there (i) or not. If possible then see if total number of jump (result[i] + 1) is less than result[N+1], then update result[N+1] else just continue to next index.

**Code:**I skipped algorithm but commented code properly.

//Define MAX 1 less so that adding 1 doesn't make it 0

#define MAX 0xFFFFFFFE;

unsigned int jump(int *array, int n)

{

unsigned int

*result = new unsigned int[n];

int i, j;

//Boundry conditions

if (n==0 || array[0] == 0)

return MAX;

result[0] = 0; //no need to jump at first element

for (i = 1; i < n; i++)

{

result[i] = MAX; //Initialization of result[i]

for (j = 0; j < i; j++)

{

//check if jump is possible from j to is

if (array[j] >= (i-j)) {

//check if better solution available

if ((result[j] + 1) < result[i])

result[i] = result[j] + 1; //updating result[i]

}

}

}

//return result[n-1]

unsigned int answer = result[n-1];

delete[] result;

return answer;

}

Above code will return optimum number of jumps only. If we want to have the jump indexes as well, we can very easily modify the code as per requirement.

**Efficiency:**Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1).

So time efficiency O(n) = O(n*(n-1)/2) = O(n^2)

We also need O(n) space for result array.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
AnonymousIf complexity is O(n^2) with this algorithm, why not just take 1 step every time. That way time complexity would be O(n) and space complexity would be o(1).

What I mean to say this seems more like using common-sense then algorithm. No offense intended. Just my 0.02$. However, I truly like you website.

Thanks,

RK

UnknownHey Anonymous.

I could not get your logic. It will be great to explain the logic with an example.

AnonymousI think I has a O(n) solution.

Consider the following algorithm.

array[n] //contain the numbers

next_furthest = 0

current_furthest = array[0]

step = 1

for i = 1 to n-1:

if i > current_furthest:

current_furthest = next_furthest

step += 1

next_furthest = max(i+array[i], next_furthest)

//after the loop the answer is store in the variable step

note: above algorithm assume that array size > 1 and array[i] > 0, add necessary if else statement to resolve

please do tell me if i has anything wrong.

Thanks,

YK