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 u reach the goal in minimum number of jumps.
For example:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index 4)
ii) 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.
A lot of input has been derived from previous review here.
public final class JumpGame {
private JumpGame() {}
/**
* Returns the shortest jump path from the source to destination
*
* @param jump The jump array
* @return Returns one of the shortest paths to the destination.
*/
public static List<Integer> getShortestJumps(int[] jump) {
final List<Integer> list = new ArrayList<Integer>();
list.add(0);
for (int i = 0; i < jump.length - 1; ) {
int iSteps = Math.min(jump.length - 1, i + jump[i]); // iSteps is all the consecutive steps reachable by jumping from i.
int maxStep = Integer.MIN_VALUE; // max step is one of the step in iSteps, which has the max potential to take us forward.
/* trying each step of iSteps */
for (int j = i + 1; j <= iSteps; j++) {
/* being greedy and picking up the best step */
if (maxStep < jump[j]) {
maxStep = j;
}
}
list.add(maxStep);
i = maxStep; // jump to the maxStep.
}
return list;
}
public static void main(String[] args) {
int[] a1 = {2,3,1,1,4};
List<Integer> expected = new ArrayList<Integer>();
expected.add(0);
expected.add(1);
expected.add(4);
Assert.assertEquals(expected, getShortestJumps (a1));
int[] a2 = {3, 1, 10, 1, 4};
expected = new ArrayList<Integer>();
expected.add(0);
expected.add(2);
expected.add(4);
Assert.assertEquals(expected, getShortestJumps (a2));
}
}