You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

&nbsp;
Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.


Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 104
	0 &lt;= nums[i] &lt;= 105


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
        # Memoization + DFS Solution
        # TLE as we have as much as n decisions depending on nums[i] which could be
        # 10^5 as an uppercase according to problem constraints
        # better off with a greedy approach

        cache = {} # i : bool

        def dfs(i):
            if i == len(nums) -1:
                return True
            if nums[i] == 0:
                return False
            if i in cache:
                return cache[i]
            for j in range(1, nums[i] + 1):
                res = dfs(i + j)
                if res:
                    cache[i] = True
                    return cache[i]
            cache[i] = False
            return cache[i]

        return dfs(0)
        """
        # Greedy Solution
        # Key with greedy is to find a local and gobal optimum
        # here we find the furthest distance we can travel with each index

        # futhest index reachable
        reachable = 0

        # iterate through all indexes and if the current index is futher than what we can travel return fasle
        for i in range(len(nums)):
            if i > reachable:
                return False

            reachable = max(reachable, nums[i] + i)
            # if the futherest distance we can jump to is greater or equal than the last index break
            if reachable >= len(nums) - 1:
                break

        return True
class Solution {
    public boolean canJump(int[] nums)
    {
        int maxjump = 0;
        for(int i=0;i<nums.length;i++)
        {
            // If the current index 'i' is less than current maximum jump 'curr'. It means there is no way to jump to current index...
            // so we should return false
            if(maxjump<i)
                return false;
            else
                maxjump = Math.max(maxjump,nums[i]+i); // Update the current maximum jump...
        }
        return true;
    }
}

//nums[i]+1 gives themax jump index possible from i
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int ans = nums[0];
        if(nums.size()>1&&ans==0) return false;
        for(int i=1; i<nums.size(); i++){
            ans = max(ans-1,nums[i]);
            if(ans<=0&&i!=nums.size()-1) return false;
        }
        return true;
    }
};
var canJump = function(nums) {
    let target = nums.length-1;
    let max = 0,index = 0;

    while(index <= target){
        max = Math.max(max,index + nums[index]);

        if(max >= target) return true;

        if(index >= max && nums[index] === 0) return false;

        index++;
    }

    return false;
};
Jump Game