Jump Game II [LC#45]

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach the last position.

Intuition

Code

def min_jump(nums: List[int]) -> int:
    n = len(nums)
    if n == 1: return 0
    left, right, jumps = 0, 0, 0
    while right < n - 1:
        max_reach = max(nums[i] + i for i in range(left, right + 1))
        left = right 
        right = max_reach
        jumps += 1
    return jumps

Time complexity