My easy to understand O(n) time and O(n) space solution


  • 0
    T
    public class Solution {
        public boolean canJump(int[] nums) {
            if(nums.length==0 || nums.length==1) return true;
            boolean[] check = new boolean[nums.length];
            int lastIndex = nums.length-1;
            int firstTrue = Integer.MAX_VALUE;
            int i = nums.length-1;
            while(i>=0 && firstTrue > 0){
                if(i+nums[i] >= nums.length-1){
                    firstTrue = i;
                    check[i] = true;
                }else{
                    if(firstTrue!=-1){
                        if(i+nums[i]>=firstTrue){
                            firstTrue = i;
                            check[i] = true;
                        }
                    }
                }
                i--;
            }
            
            return check[0];
            
        }
    }

Log in to reply
 

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