Java solution with O(n) time, O(1) space and Explanation


  • 0
    N
    public class Solution {
        public boolean canJump(int[] A) {
            if(A==null || A.length == 0) return false;
            if(A.length == 1) return true;
            if(A[0] == 0) return false;
            
            int cur = A[0];
            
            for(int i=1;i<A.length;i++){
                cur--; // in current position, it can cover 'cur' further steps
                cur = Math.max(cur,A[i]);  // update cur, make sure it covers the longest further steps
                if(cur == 0 && i!= A.length-1) return false; // when cur is 0, means we are trapped. The only exception is we already at the end.
            }
            
            return true;
        }
    }

Log in to reply
 

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