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.