minimum of jumps required to reach end of array - get index positions

Question

The problem is get the minimum jumps and the corresponding indices in the array that lead to end of array with lesser jumps. for ex: {3,2,3,1,5,4} would take 2 jumps.

Jump 1 from index 0 to index 2 
jump 2 from index 2 to index 5 

By Jump, I mean hopping; i.e how many hops are needed. if you are a particular index, you get to hop by the value in that index.

Here is my implementation in Java, which gives the minimum number of jumps correctly, but I am having difficulty updating the list that I have with indices corresponding to the hop positions. how can I get it to working?

public static int minJumps2(int[] arr, List<Integer> jumps){
        int minsteps=0;
        boolean reachedEnd=false;
        if (arr.length<2)
            return 0;
        int farthest=0;
        for (int i=0;i<=farthest;i++){
             farthest=Math.max(farthest, arr[i]+i);
             if (farthest>=arr.length-1){
                 jumps.add(i);
                 reachedEnd=true;
                 break;
             }
             //jumps.add(farthest);
             minsteps++;

        }
        if (!reachedEnd){
            System.out.println("unreachable");
            return -1;
        }
        System.out.println(minsteps);
        System.out.println(jumps);
        return minsteps;
    }

public static void main(String[] args){

        int[] arr= {3,2,3,1,5};
        List<Integer> jumps=new ArrayList<Integer>();
        minJumps2(arr,jumps);

    }

I am using the Jump game algorithm as described here: Interview puzzle: Jump Game

Answer 1

I see you already accepted an answer, but I have code that does what you need:

-It prints out the paths of min jumps (not just one, but all).

-It will also tell you if end of array is unreachable.

It uses DP, complexity = O(nk), where n is length of array, and k is numerical value of largest element in array.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinHops {

    private static class Node {
        int minHops;
        int value;
        List<Node> predecessors = new ArrayList<>();

        Node(int distanceFromStart, int value) {
            this.minHops = distanceFromStart;
            this.value = value;
        }
    }

    public static void allMinHopsToEnd(int[] arr) {
        Node[] store = new Node[arr.length];
        store[0] = new Node(0, arr[0]);
        for (int i = 1; i < arr.length; i++) {
            store[i] = new Node(Integer.MAX_VALUE, arr[i]);
        }

        for (int index = 0; index < arr.length; index++) {
            try {
                updateHopsInRange(arr, store, index);
            } catch (RuntimeException r) {
                System.out.println("End of array is unreachable");
                return;
            }
        }

        Node end = store[store.length-1];
        List<ArrayList<Integer>> paths = pathsTo(end);
        System.out.println("min jumps for: " + Arrays.toString(arr));
        for (ArrayList<Integer> path : paths) {
            System.out.println(path.toString());
        }

        System.out.println();
    }

    private static void updateHopsInRange(int[] arr, Node[] store, int currentIndex) {
        if (store[currentIndex].minHops == Integer.MAX_VALUE) {
            throw new RuntimeException("unreachable node");
        }

        int range = arr[currentIndex];
        for (int i = currentIndex + 1; i <= (currentIndex + range); i++) {
            if (i == arr.length) return;
            int currentHops = store[i].minHops; 
            int hopsViaNewNode = store[currentIndex].minHops + 1;

            if (hopsViaNewNode < currentHops) { //strictly better path
                store[i].minHops = hopsViaNewNode;
                store[i].predecessors.clear();
                store[i].predecessors.add(store[currentIndex]);
            } else if (hopsViaNewNode == currentHops) { //equivalently good path
                store[i].predecessors.add(store[currentIndex]);
            }
        }
    }

    private static List<ArrayList<Integer>> pathsTo(Node node) {
        List<ArrayList<Integer>> paths = new ArrayList<>();
        if (node.predecessors.size() == 0) {
            paths.add(new ArrayList<>(Arrays.asList(node.value)));
        }

        for (Node pred : node.predecessors) {
            List<ArrayList<Integer>> pathsToPred = pathsTo(pred);
            for (ArrayList<Integer> path : pathsToPred) {
                path.add(node.value);
            }

            paths.addAll(pathsToPred);
        }

        return paths;
    }

    public static void main(String[] args) {
        int[] arr = {4, 0, 0, 3, 6, 5, 4, 7, 1, 0, 1, 2};
        int[] arr1 = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        int[] arr2 = {2, 3, 1, 1, 4};
        int[] arr3 = {1, 0, 0, 4, 0};
        allMinHopsToEnd(arr);
        allMinHopsToEnd(arr1);
        allMinHopsToEnd(arr2);
        allMinHopsToEnd(arr3);
    }

}

Answer 2

Though I did not understand your question clearly, but it seems that you need to add the index to jumps when you increment the minsteps++.

You need to un comment jumps.add(farthest); and pass the i instead of farthest. Also you may need to remove the jumps.add(i) with in if condition. Hope this helps.

EDIT: It seems your logic is fine except for the first jump which is at index 0 always. So add 0 to your jumps just before your loop.

UPDATE Okay, I was not tested and also not gone through the algorithm link you provided. The algo explains that we need to consider an element e and index i and get the max of the elements from current position to arr[e] and that is not happening. I tried to replicate the exact step the solution mentioned. Hope this might help you.

public static int minJumps2(int[] arr, List<Integer> jumps) {
        boolean reachedEnd = false;
        if (arr.length < 2)
            return 0;

        //calculate (index + value)
        int[] sums = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sums[i] = i + arr[i];
        }
        // start with first index
        jumps.add(0);

        while (true) {
            int currentPosition = jumps.get(jumps.size() - 1);
            int jumpValue = arr[currentPosition];

            // See if we can jump to the goal
            if (arr.length - 1 - currentPosition <= jumpValue) {
                jumps.add(arr.length - 1);
                reachedEnd = true;
                break;
            } else {
                int maxIndex = currentPosition;
                int currentMax = sums[maxIndex];
                // max of the reachable elements
                for (int i = currentPosition; i <= currentPosition + jumpValue; i++) {
                    if (sums[i] > currentMax) {
                        maxIndex = i;
                        currentMax = sums[i];
                    }
                }
                if (maxIndex == currentPosition) { 
                    break; 
                }

                jumps.add(maxIndex);
            }
        }
        System.out.println(jumps.size());
        System.out.println(jumps);
        return jumps.size();
    }