Shortest Jump Path

You are given an array of Integers with value greater or equal to 0. for example: [5, 6, 0, 4, 2, 6, 1, 0, 0, 4] the value at index i represents the maximum step you can jump from index i. Now start from index 0, find the shortest path that reach the out of the array or there is no such solution.

Solution

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */

        /* read in data using Scanner */
        Scanner in = new Scanner(System.in);
        List<Integer> array = new ArrayList<Integer>();
        while(in.hasNext()){
            array.add(in.nextInt());
        }
        if(array.size()==0){//malformed input
            System.out.println("failure");
            return;
        }
        //Use helper functio findShortestHop to find the solution path
        List<Integer> ans = findShortestHop(array);
        if(ans==null){//did not find path
            System.out.println("failure");
            return;
        }
        StringBuilder res =  new StringBuilder();
        for(int a :ans){
            res.append(a).append(", ");
        }
        res.append("out");
        System.out.println(res.toString());
    }

    public static List<Integer> findShortestHop(List<Integer> array){
        int N = array.size();
        //minStep record the minimum step to reach out the array
        int minStep  = Integer.MAX_VALUE;
        // lastIndex record the last index of the solution path
        int lastIndex = -1;

        boolean[] reachable = new boolean[N];//mark the index that is reachable
        reachable[0] = true;//start from index 0
        /*
        we use an two dimension array to record the previous index and the minimum step to reach current index
        previous index: jumpFrom[i][0]
        minimum step to reach index i: jumpFrom[i][1]
        Initialize jumpFrom[0] to {0,1}
        */
        int[][] jumpFrom = new int[N][2];
        jumpFrom[0][0] = 0;
        jumpFrom[0][1] = 1;

        int index = 0;
        for(;index<N;index++){
            //this index is unreachable, which means all the index after are unreachable. stop searching
            if(!reachable[index]) break;
            int maxJump = array.get(index);
            for(int j=1;j<=maxJump;j++){
                if (index+j>=N) {//the next hop reach the end
                    if(jumpFrom[index][1]<minStep){
                        minStep = jumpFrom[index][1];
                        lastIndex = index;
                    }
                    break;
                }
                if(reachable[index+j]) continue;//we have already find the shorest path to this index
                else{
                    reachable[index+j] = true;
                    jumpFrom[index+j][0] = index;
                    jumpFrom[index+j][1] = jumpFrom[index][1]+1;
                }
            }
        }
        //if the loop is break or lastIndex is not valid, we did not find the solution path
        if(index!=N || lastIndex==-1) return null;
        LinkedList<Integer> ans =  new LinkedList<Integer>();
        while(jumpFrom[lastIndex][0]!=lastIndex){
            ans.addFirst(lastIndex);
            lastIndex = jumpFrom[lastIndex][0];
        }
        ans.addFirst(0);
        return ans;
    }
}