Share my clean java solution with explanation


  • 0
    O

    public boolean canJump(int[] nums) {

        //observed from the last k element, if nums[n-k] < k, then we cannot reach the end from it
        //search from the ending point, if nums[n-k] >= k, then we can reach the end from here 
        //now we got a subproblem, can we jump to this point(nums[n-k]) from the head
        //time O(n), space O(1)
        if(nums.length<=1) return true;
        boolean res = true;//we can always reach the last point from the last point
        int lastReachable = nums.length-1;
        for(int i = nums.length-1; i >=0; i--){
            if((nums[i] + i) >= lastReachable){
                lastReachable = i;
                res = true;
            }
            else res = false;
        }
        return res;
    }
    

    Here is a pic to explain this
    index 0 1 2 3 4 5 6 7 8
    nums 2 0 1 4 2 1 0 1 4
    result T F T T F F F T T
    The "res" starts from the last index


Log in to reply
 

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