Interview puzzle: Jump Game

Question

Jump Game: 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. The optimum result is when you reach the goal in minimum number of jumps.

What is an algorithm for finding the optimum result?

An example: given array A = {2,3,1,1,4} the possible ways to reach the end (index list) are

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

Since second solution has only 2 jumps it is the optimum result.

Answer 1

Overview

Given your array a and the index of your current position i, repeat the following until you reach the last element.

Consider all candidate "jump-to elements" in a[i+1] to a[a[i] + i]. For each such element at index e, calculate v = a[e] + e. If one of the elements is the last element, jump to the last element. Otherwise, jump to the element with the maximal v.

More simply put, of the elements within reach, look for the one that will get you furthest on the next jump. We know this selection, x, is the right one because compared to every other element y you can jump to, the elements reachable from y are a subset of the elements reachable from x (except for elements from a backward jump, which are obviously bad choices).

This algorithm runs in O(n) because each element need be considered only once (elements that would be considered a second time can be skipped).

Example

Consider the array of values a, indicies, i, and sums of index and value v.

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

Start at index 0 and consider the next 4 elements. Find the one with maximal v. That element is at index 1, so jump to 1. Now consider the next 11 elements. The goal is within reach, so jump to the goal.

Demo

See here or here with code.

Answer 2

Dynamic programming.

Imagine you have an array B where B[i] shows the minimum number of step needed to reach index i in your array A. Your answer of course is in B[n], given A has n elements and indices start from 1. Assume C[i]=j means the you jumped from index j to index i (this is to recover the path taken later)

So, the algorithm is the following:

set B[i] to infinity for all i
B[1] = 0;                    <-- zero steps to reach B[1]
for i = 1 to n-1             <-- Each step updates possible jumps from A[i]
    for j = 1 to A[i]        <-- Possible jump sizes are 1, 2, ..., A[i]
        if i+j > n           <-- Array boundary check
            break
        if B[i+j] > B[i]+1   <-- If this path to B[i+j] was shorter than previous
            B[i+j] = B[i]+1  <-- Keep the shortest path value
            C[i+j] = i       <-- Keep the path itself

The number of jumps needed is B[n]. The path that needs to be taken is:

1 -> C[1] -> C[C[1]] -> C[C[C[1]]] -> ... -> n

Which can be restored by a simple loop.

The algorithm is of O(min(k,n)*n) time complexity and O(n) space complexity. n is the number of elements in A and k is the maximum value inside the array.

Note

I am keeping this answer, but cheeken's greedy algorithm is correct and more efficient.