Java(Time:O(n), Space:O(1)): With clear and easy understanding comments


  • 3
    C

    Thanks to all the discussions a lot. I have read some posts and I find it may still is a little hard to understand the underlying design philosophy. So I hope this code can help a little.

        public int jump (int[] nums) {
        if (nums.length == 1) {//when length==1, ignore what's in nums[0]
            return 0;
        }
    
        int step = 0;//init step = 0 before actual start
        int position = 0;//start position in current step
        int reachable = 0;//furthest can reach in current step
        int furthest = 0;//furthest can reach in next step, it will be new reachable in next loop
    
        //the loop invariant is the reachable corresponding to every step
        while (position <= reachable) {//one loop indicate one step, it starts with step==0
            furthest = Math.max(furthest, position + nums[position]);//get furthest for next loop
            if (furthest >= nums.length - 1) {//can reach the end in next step
                return step + 1;
            }
            if (position == reachable) {//this step end
                if (furthest <= reachable) {//can not go further
                    return -1;
                } else {//add this step and go further
                    ++step;
                    reachable = furthest;
                }
            }
            ++position;//continue this step
        }
        return -1;
    }

  • 0
    W

    A array like 5,4,3,2,1,5,4,3,2,1, I think Time is O(nm)


  • 0
    C

    I don't know whether we got different understanding about the "n" in O(n), which I indicate the length of the nums[] array.
    Notice the code

    ++position;//continue this step
    

    at the last but one line. Every single loop will increase position. So at the worst case, the time consume will equal the length of the array.
    And for your case, when the code reach the second "5", it should be return 2 and finish.Am I right?


Log in to reply
 

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