JumpGame.java

package medium;

public class JumpGame {
    
    public static boolean canJump_greedy(int[] nums) {
        int farthest = nums[0];
        for(int i = 0; i < nums.length; i++){
            if(i <= farthest && nums[i]+i > farthest) {
                //i <= farthest is to make sure that this current i is within the current range
                // nums[i]+i > farthest is to make sure that it's necessary to update farthest with current nums[i]+i
                farthest = nums[i]+i;
            }
        }
        return farthest >= nums.length-1;
    }

    //this normal dp ends in TLE for extreme test cases
    public static boolean canJump_dp(int[] nums) {
        boolean[] can = new boolean[nums.length];
        can[0] = true;
        for(int i = 0; i < nums.length; i++){
            int reach = nums[i];
            if(can[i]){
                for(int j = i+1; j < nums.length && j <= i+reach; j++){
                    can[j] = true;
                }
            }
        }
        return can[nums.length-1];
    }

    public static void main(String...strings){
//        int[] nums = new int[]{1,2};
        int[] nums = new int[]{0,2,3};
        System.out.println(canJump_greedy(nums));
    }
}