Jump Game

class Solution {
    public boolean canJump(int[] nums) {
        var len = nums.length;
        //cornor
        if (len == 1){
            return true;
        }
        //cornor
        var canReach = new boolean[len-1];
        var target = len - 1;
        for (int cur = (len-2); cur >= 0; cur--){
            var maxJump = nums[cur];
            var required = target - cur;
            var jump = (maxJump > required) ? required : maxJump;
            while(jump > 0){
                var next = cur+jump;
                if (next == target){
                    canReach[cur] = true;
                    break;
                } else if (canReach[next]){
                    canReach[cur] = true;
                    break;
                }
                jump--;
            }
        }
        return canReach[0];
    }
}

Leet code

Given with an integer array with each index having the max jump that can be made. Need to find if the last index can be reached from the first index.

Achievement

The above code solution is done by me using the Dynamic programming technique. The provided code took 144ms and beats 30% of the total solutions submitted.

Yet Better Approach

The above question can be solved using the greedy algorithm. The below code demonstrates the same and beats 73% of the total solutions submitted by taking a runtime of 2ms

class Solution {
    public boolean canJump(int[] nums) {
        var reach = 0;
        var len = nums.length;
        for(int cur = 0; cur <= reach; cur++){
            reach = Math.max(reach, (cur + nums[cur]));
            if (reach >= (len -1)){
                return true;
            }
        }
        return false;
    }
}