12 lines Java solution O(n) time O(1) space


  • 2
    M
    public int jump(int[] nums) {
        int max = 0, next = 0, count = 0; 
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i > max) {
                max = next; //only when i > max, need to update max
                count++; //keep record of the num of jumps
            } 
            next = Math.max(next, i + nums[i]);  //the next farthest possible position
        }
        return count;
    }

  • 6
    Y

    Your solution is simple and elegant, and it CAN pass all the test cases. But it assumes that we can jump to the end of the array. (I believe the test cases also assumes this)
    Try this input [3, 2, 1, 0, 4]. Your code returns 2. But actually there's no way we can jump to the end..

    Below is a solution that can test whether an input can jump to the end, if not, returns -1; reference: http://bangbingsyb.blogspot.com/2014/11/leetcode-jump-game-i-ii.html

    public int jump_v2(int[] nums){
    	int curMax = 0, njumps=0, i=0;
    	while (curMax < nums.length-1){
    		int lastMax = curMax;
    		for(; i<=lastMax; i++){
    			curMax = Math.max(curMax, i+nums[i]);
    		}
    		njumps++;
    		if(lastMax == curMax) return -1;
    	}
    	return njumps;
    }
    

  • 0
    D

    just need to change the last line of code:

    return max>=len-1?count:-1;


Log in to reply
 

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