Java O(n) greedy solution with explanation.


  • 0
    Z

    Keep updating the furthest reachable by each step before move on to the next step:

    1. Initially step = 0: we can only reach index 0, so currStepMax = 0. But for next step we can reach 0 + nums[0]. This is updated to "reachAble".
    2. Index = 1 > curreStepMax(0), which means 0 step is not able to reach index = 1. At this time, we have to increase step to 1. What about "currStepMax" now? It should be updated to the "reachAble" from step 0;
    3. When index increasing, we keep updating "reachAble", which record the furthest index we can reach by current step.
    4. If index reach "currStepMax", we have to increase step again.
    5. If "reachAble" exceed the last index, we break the loop. Which means from current step, we take one more step can reach the destination.
    public class Solution {
        public int jump(int[] nums) {
            if (nums.length == 1) return 0;
            
        // init
            int reachAble = 0; // reachAble updates how far can be reached by now
            int index = 0;  // update nums index
            int step = 0;  // record current step number 
            int currStepMax = 0; // update how far can be reached by current step
            
        // if the index pass the updated furthest, we cannot move any futher
        // by this way we can also find out whether the final index is reachable or not:
        // (outside while loop to check: reachAble >= nums.length - 1)
            while (index <= reachAble) { 
    
        // for current step, if the index has reached the furthest reachable (currStepMax), we have no way but to take another step
        // after taking the step, the currStepMax should be updated by the furthest reachable from last step, which is (reachAble)
                if (index > currStepMax) {
                    step++; 
                    currStepMax = reachAble;
                }  
           
        // for each index, we always update reachAble (the furthest index can be reached)     
                if (index + nums[index] > reachAble) {
                    reachAble = index + nums[index];
                } 
                
         // when reachAble exceed the last index, we find our solution       
                if (reachAble >= nums.length - 1) {
                    break;
                } 
                
                index++;
            }
            
            return step + 1;  // take the last step, we reach the destination (guaranteed minimum steps)
        }
    }
    

Log in to reply
 

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