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.

Your goal is to reach the last index in the minimum number of jumps.

Example:


Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def jump(self,nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return 0
         else:
             step = 0
             pos = 0
             while pos != len(nums) - 1:
                 bestStep = -1
                 bestValue = -1
                 for i in range(nums[pos], 0, -1):
                     if len(nums) - 1 == pos + i:
                         bestStep = i
                         break
                     if (pos + i < len(nums) and nums[pos + i] != 0 and nums[pos + i] + i > bestValue):
                         bestStep = i
                         bestValue = nums[pos + i] + i
                 print(bestStep)
                 pos += bestStep 
                 step += 1
 
             return step
 
 


class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         res = 0
         n = len(nums)
         i, j = 0, 0
         
         while j < n - 1:
             print((i, j))
             ii, jj = i, j
             for k in range(ii, jj + 1):
                 j = max(j, min(n - 1, k + nums[k]))
             i = jj + 1
             res += 1
         return res


class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums: return 0
         if len(nums) == 1: return 0
         step, far, maxV = 0, 0, 0
         
         for i in range(len(nums)):
             if i + nums[i] > maxV and i + nums[i] >= len(nums) - 1: return step + 1
             maxV = max(maxV, i + nums[i])
             if i == far:
                 step += 1
                 far = maxV
         return step

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         p = [0]
         for i in range(len(nums) - 1):
             while(i + nums[i] >= len(p) and len(p) < len(nums)):
                 p.append(p[i] + 1)
         return p[-1]

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         
         if len(nums)<=1:
             return 0
         dist=1
         explored ={}
         Q =[]
         explored[0]=dist
         Q.append(0)
         levelup = 0
         while Q[-1]+1 < len(nums):
             print(Q)
             v = Q[0]
             Q.pop(0)
             before=len(explored)
             for i in range(nums[v]):
                 if not (v+i+1) in explored:
                     explored[v+i+1] = dist
                     Q.append(v+i+1)
             if v== levelup:
                 dist+=1
                 levelup=Q[-1]
             print(Q)
         return explored[len(nums)-1]
         """
         cur = 0
         ans = 0
         maxstep =0
         for i in range (0,len(nums)-1):
             maxstep = max(maxstep,i+nums[i])
             if i ==cur:
                 ans +=1
                 cur = maxstep
         return ans

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0 or len(nums) == 1:
             return 0;
         s = 0; e = 0; step = 0
         while (e < len(nums) - 1):
             fst = e
             step += 1
             for i in range(s, e + 1):
                 if fst < nums[i] + i:
                     fst = nums[i] + i
             s = e + 1
             e = fst
         return step

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         current_step = 0
         last_step = 0
         i = 0
         n_jumps = 0
         while last_step < len(nums)-1:
             while i <= last_step:
                 current_step = max(i+nums[i],current_step)
                 i += 1
             last_step = current_step
             n_jumps += 1
         return n_jumps


class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n, start, end, step = len(nums), 0, 0, 0
         while end < n - 1:
             step += 1
             maxend = end + 1
             for i in range(start, end + 1):
                 if i + nums[i] >= n - 1:
                     return step
                 maxend = max(maxend, i + nums[i])
             start, end = end + 1, maxend
         return step

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if nums is None or len(nums) <= 1:
             return 0
         
         start = currEnd = nextEnd = jump = 0
         while currEnd - start + 1 > 0:
             jump += 1
             for i in range(start, currEnd+1):
                 nextEnd = max(nums[i] + i, nextEnd)
                 if nextEnd >= len(nums) - 1:
                     return jump
             start = currEnd + 1
             currEnd = nextEnd
         return jump

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) <= 2:
             return len(nums)-1
         stack = []
         i = len(nums) - 2
         while i >= 0:
 #            print(nums,stack)
             if nums[i] == 1:
                 stack.append(i)
             elif nums[i] >= (len(nums)-1-i):
                 if stack:
                     stack.clear()    
                 stack.append(i)
             else:
                 j = 0
                 while stack and j < len(stack): 
                     if nums[i] >= (stack[j]-i):
                         stack = stack[0:j+1]
                         stack.append(i)
                         break
                     else:
                         j += 1
             i -= 1
 #        print(stack)
         return len(stack)
                     


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

class Solution:
     def jump(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         dic = {}
         length = len(nums)
         dic[length - 1] = 0
         for j in range(length - 1)[::-1]:
             #print(length - j + 1)
             if(nums[j] >= nums[j + 1] + 1 and not j + 1 == length - 1):
                 minstep = dic[j + 1] - 1
                 for k in range(max(3, nums[j+1] + 2) ,min(length - j , nums[j] + 1)):
                     #print(j,k)
                     if dic[j + k] < minstep:
                         minstep = dic[j + k]
                 dic[j] = minstep + 1
                 continue
             minstep = dic[j + 1]
             for k in range(2,min(length - j , nums[j] + 1)):
                 #print(j,k)
                 if dic[j + k] < minstep:
                     minstep = dic[j + k]
             dic[j] = minstep + 1
         #print(dic)
         return dic[0]