Jump game to find minimum hops from source to destination

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 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));
    }

}

Answer 1

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;
}

Answer 2

Your unit tests could be less verbose, using java.util.Arrays.asList(...).

int[] a1 = {2,3,1,1,4};
Assert.assertEquals(Arrays.asList(0, 1, 4), getShortestJumps(a1));