55. Jump Game

Intuition

The problem requires determining whether it is possible to reach the last index of the array starting from the first index. Each element in the array represents the maximum number of steps that can be jumped forward from that element. To solve this problem, we need to keep track of the farthest point that can be reached as we iterate through the array.

Approach

1. Initialize two variables: maxReach to keep track of the farthest index we can reach, and target to store the last index of the array.
2. Iterate through the array using an index idx: - For each position, update maxReach to be the maximum of maxReach and idx + nums[idx]. - If maxReach is greater than or equal to target, return true because we can reach or exceed the last index. - If maxReach is less than or equal to the current index and the current value of nums[idx] is 0, return false because we are stuck and cannot move forward.
3. If the loop completes without returning, it means maxReach was never able to reach the target, so return false.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are only using a few extra variables that do not scale with the input size.

Code

C++

class Solution {
public:
    bool canJump(vector& nums) {
        int n = nums.size();
        vector dp(n, 0);
        dp[0] = 1;
        for(int i=0; i

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable = [False for i in range(len(nums))]
        reachable[0]=True

        for i in range(len(nums)):
            if not reachable[i]:
                continue 
            
            for j in range(i+1, i+nums[i]+1):
                if j >= len(nums):
                    return True 
                else:
                    reachable[j]=True
                
        return reachable[len(nums)-1]   

Java

class Solution {
    public boolean canJump(int[] nums) {

        boolean[] dp = new boolean[nums.length];
        dp[nums.length - 1] = true;
        for (int i = dp.length - 1; i >= 0; i--) {
            if (dp[i]) {
                for (int j = 0; j < i; j++) {
                    if (nums[j] >= i - j) {
                        dp[j] = true;
                        if (dp[0])
                            return true;
                    }
                }
            }
        }
        return dp[0];
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    let idx = 0;
    let max = 0;
    let target = nums.length - 1;
    while (idx < nums.length) {
        max = Math.max(max, idx + nums[idx]);
        console.log(max, idx)
        if (max >= target) {
            return true;
        }
        if (max <= idx && nums[idx] === 0) {
            return false;
        }
        idx++;
    }
    return false;
};