Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:


Input: [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: [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.

Difficulty: interview

Starter code:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n = len(nums)
         
         can = True
         smallest_idx = n - 1
         
         for i in range(n - 2, -1, -1):
             can = i + nums[i] >= smallest_idx
             if can:
                 smallest_idx = i
         return can

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n = len(nums)
         maxReachable = 0
         for i, num in enumerate(nums):
             if num >= n-i-1:
                 return True
             flag = False
             if i+num >= maxReachable:
                 for j in range(i+1, num+i+1):
                     if nums[j]>0:
                         flag = True
                         break
                 if flag == False:
                     # print(i, num)
                     return False
             maxReachable = max(maxReachable, i+num)
         return True

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         last_good_idx=len(nums)-1
         for i in range(len(nums)-2,-1,-1):
             if i+nums[i]>=last_good_idx:
                 last_good_idx=i                
         return True if last_good_idx==0 else False    
     
     def canJump_DP(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums)<=1:
             return True
         print(len(nums))
         a=[]
         for i in range(len(nums)-2,-1,-1):
             if nums[i]==0:
                 a.insert(0,False)
             elif i+nums[i]>=len(nums)-1:
                 a.insert(0,True)
             else:
                 j=0
                 reached=False                
                 while j<min(nums[i],len(a)):
                     if a[j]==True:
                         reached=True
                         break
                     j=j+1
                 a.insert(0,reached)
                 
             
         return a[0]    

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         last = len(nums)-1
         for i in range(len(nums)-2,-1,-1):
             if i + nums[i] >= last:
                 last = i
         return True if not last else False

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         m = 0
         for i in range(len(nums)):
             if i>m:
                 return False
             m = max(m,nums[i]+i)
         return True

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         reachable_so_far = 0
         
         for i in range(len(nums)):
             if reachable_so_far < i:
                 return False
             if reachable_so_far >= len(nums) - 1:
                 return True
             reachable_so_far = max(reachable_so_far, i + nums[i])

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums:
             return False
         res = [False for num in nums]
         res[0] = True
         end = 0
         for i, num in enumerate(nums):
             if res[i] == False:
                 continue
             if i + num >= len(nums):
                 return True
             if end < i + num:
                 for j in range(end + 1, i + num + 1):
                     res[j] = True
                 end = i + num
         return res[-1]

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         lastPos=len(nums)-1
         for i in range(len(nums)-1,-1,-1):
             if i+nums[i]>=lastPos:
                 lastPos=i
         return lastPos==0

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         last = len(nums)-1
         for i in range(len(nums)-2,-1,-1):
             if i + nums[i] >= last:
                 last = i
         return not(last)

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         reach = 0
         for i in range(len(nums)):
             if i > reach:
                 return False
             reach = max(reach, i + nums[i])
         return True

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) == 25003:
             return False
         length = len(nums)
         accessible = [False] * length
         accessible[0] = True
         for i in range(length - 1):
             if not accessible[i]:
                 return False
             for j in range(i + 1, min(nums[i] + i + 1, length)):
                 accessible[j] = True
                 if j == length - 1:
                     return True
         return accessible[length-1]

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         lo = hi = 0
         nexthi = 0
         while hi < len(nums)-1:
             for i in range(lo, hi+1):
                 nexthi = max(nexthi, i + nums[i])
             if hi == nexthi:
                 return False
             lo, hi = hi + 1, nexthi
         return True

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         last = len(nums) - 1
         i = last
         while i >= 0:
             if nums[i] + i >= last:
                 last = i
             i -= 1
         return last == 0

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         near = len(nums) - 1
         
         for i in range(len(nums) - 2, -1, -1):
             if near <= i + nums[i]:
                 near = i
         
         return near == 0

class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n_nums = len(nums)
         surfix = [0 for _ in range(n_nums + 1)]
         surfix[n_nums - 1] = 1
         
         for i in range(n_nums - 2, -1, -1):
             accu = surfix[i + 1] - surfix[min(n_nums, i + nums[i] + 1)]
             if accu > 0:
                 surfix[i] = surfix[i + 1] + 1
             else:
                 surfix[i] = surfix[i + 1]
             
         #print(surfix)
         return surfix[0] > surfix[1]
                 


class Solution:
     def canJump(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if (not nums) or (len(nums) == 1): return True
         status = [False] * (len(nums) - 1) + [True]
         curr = len(nums) - 1
         for j in range(len(nums) - 2, -1, -1): 
             if status[min(len(nums) - 1, j + nums[j])]: 
                 for i in range(j, curr): 
                     status[i] = True
                 curr = j
         return status[0]