Java slightly changed code from JumpGame 1 greedy solution


  • 0
    Z

    At each iteration we greedily expand the maximum reachable index, at the same time we keep queue of all updated reachable indexes. Thus, while we don't reach the closest updated reachable index, the current index is reachable by the same number of jumps as the closest updated reachable index. After we pass the closest reachable updated index we poll it out from the queue, and assign to other indexes the number of jump of the next closest updated reachable index. If if we need to update the farest reachable index, then we update its reachable index too.
    After you understand that solution, you may have a look at more elegant optimized solution here
    Sorry for messy text and code :P

    public class Solution {
        public int jump(int[] nums) {
            if(nums.length == 1) return 0;
            int reach = 0;
            int jump[] = new int[nums.length];
            Arrays.fill(jump, -1);
            jump[0] = 0;
            int jmp = 0;
            int pReach = 0;
            Queue<Integer> rs = new LinkedList<>();
            rs.add(reach);
            for(int i = 0;i<=reach ;i++){
                 jump[i] = (jump[i] == -1)?jmp:jump[i];
                if(i + nums[i] > reach){
                    pReach = reach;
                    reach = Math.min(i+nums[i], nums.length-1);
                    int prev = jump[reach];
                    jump[reach] = 1+jump[i];
                    if(prev != -1) jump[reach] = Math.min(prev, jump[reach]);
                    rs.add(reach);
                } 
                
                if(!rs.isEmpty() && rs.peek()<= i){
                    rs.poll();
                    jmp = jump[rs.peek()];
                }
                
            }
            return jump[nums.length-1];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.