Jump Game II

Time Complexity $O(n)$

class Solution:
 
    def jump(self, nums: List[int]) -> int:
 
        j = 0
 
        current_end = 0
 
        farthest = 0
 
        for i in range(len(nums) - 1):
 
            farthest = max(farthest, i + nums[i])
 
  
 
            if i == current_end:
 
                j += 1
 
                current_end = farthest
 
        return j

Related: