Return to Answer

• 1

• 98.1k
• 17
• 219
• 419

##Code-Style

For the most part, this is good:

• return types are good.
• Collections are well typed
• method names are good
• apart from list, a1, and a2, variable names are good

The list is a bad name for a List. The fact that it is a list is obvious... but, what is the list...? I prefer result to list.

a1 and a2 are not bad, but they are not good either. They are just 'OK'.

##Algorithm

I have worked the code through, and figure there is a plane-jane O(n) solution to the problem. Your algorithm is something larger than O(n), It is closer to O(n * m) where m is the longest jump.

The alternate algorithm I cam up with sets up a 'range' for the next jump.... It seaches all the values from the current cursor to the current range, and it looks for the jump within that range that would extend the range the furthest.

The method looks like:

public static List<Integer> getShortestJumps(int[] jump) {
 final List<Integer> list = new ArrayList<Integer>();
 if (jump.length == 0) {
 return list;
 }
 int cursor = 0;
 int best = 0;
 int range = 0;
 int remaining = 1;
 while (cursor + 1 < jump.length) {
 if (cursor + jump[cursor] > range) {
 // jumping from here would extend us further than other alternatives so far
 range = cursor + jump[cursor];
 best = cursor;
 if (range >= (jump.length - 1)) {
 // in fact, this jump would take us to the last member, we have a solution
 list.add(best);
 break;
 }
 }
 if (--remaining == 0) {
 // got to the end of our previous jump, move ahead by our best.
 list.add(best);
 remaining = range - cursor;
 }
 
 cursor++;
 }
 // always add the last member of the array
 list.add(jump.length - 1);
 return list;
}