Accepted Java solution with explanation


  • 0
    V

    public class Solution {

    public boolean canJump(int[] A) {
        if(A.length == 0){
            return false;
        }
        
        if(A.length == 1){
            return true;
        }
        
        int last = A.length - 1;
        int p = 0;
        int jump = 0;
        
        for(int i = 0; i < last; i++){
    
            if(A[i] == 0){
                for(int j = i - 1; j >= 0; j--){                  
                    jump = Math.max(jump,A[j]+j);
                }
                if(jump <= i){
                    return false;
                }
            }
    
        }
        
       return true;
        
    }
    

    }

    Because the input is non-negative array, the only way that can prevent this method reaching the last position is there exists a zero element, and the elements before it can not "jump" across the zero element.

    So we first find these zero elements, for a particular zero element, use "jump" to represent the longest distance these elements which before the zero one can jump (A[i] + i), if the jump is not bigger than this element's position, then we can conclude that we can't jump over this zero element, so we can't reach the last element.


Log in to reply
 

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