My solution in Java, O(N)


  • 0
    C

    Idea: find the the smallest index which can reach the end backward. If we find this index, regard it as the end.

            // jump game
    	public boolean canJump(int[] nums) {
    		if(nums == null || nums.length == 0) return false;
    		if(nums.length == 1) return true;
    		
    		int end = nums.length - 1;
    		for(int i = nums.length - 2; i >= 0; i--) {
    			int steps = end - i;
    			if(nums[i] >= steps) {
    				end = i;
    			}
    		}
    		if(end == 0) return true;
    		else return false;       
        }
    

Log in to reply
 

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