Jump Game II

Problem Statement

You are given an array of integers nums, where nums[i] represents the maximum length of a jump towards the right from index i. For example, if you are at nums[i], you can jump to any index i + j where:

  • j <= nums[i]
  • i + j < nums.length

You are initially positioned at nums[0].

Return the minimum number of jumps to reach the last position in the array (index nums.length - 1). You may assume there is always a valid answer.

Example 1:

Input: nums = [2,4,1,1,1,1]


Output: 2

Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.

Example 2:

Input: nums = [2,1,2,1,0]


Output: 2

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 100

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

Recursion

def jump(nums: list[int]) -> int:
    def dfs(i: int) -> int:
        if i == len(nums) - 1:
            return 0
        if nums[i] == 0:
            return float('inf')


        end = min(len(nums) - 1, i + nums[i])
        res = float('inf')
        for j in range(i + 1, end + 1):
            res = min(res, 1 + dfs(j))
        return res


    return dfs(0)

Time complexity: O(n!) Space complexity: O(n)

Dynamic Programming (Top-Down)

def jump(nums: list[int]) -> int:
    memo = {}


    def dfs(i: int) -> int:
        if i in memo:
            return memo[i]
        if i == len(nums) - 1:
            return 0
        if nums[i] == 0:
            return 1000000


        res = 1000000
        end = min(len(nums), i + nums[i] + 1)
        for j in range(i + 1, end):
            res = min(res, 1 + dfs(j))
        memo[i] = res
        return res


    return dfs(0)

Time complexity: O(n ^ 2) Space complexity: O(n)

Dynamic Programming (Bottom-Up)

def jump(nums: list[int]) -> int:
    n = len(nums)
    dp = [1000000] * n
    dp[-1] = 0


    for i in range(n - 2, -1, -1):
        end = min(n, i + nums[i] + 1)
        for j in range(i + 1, end):
            dp[i] = min(dp[i], 1 + dp[j])
    return dp[0]

Time complexity: O(n ^ 2) Space complexity: O(n)

Breadth First Search (Greedy)

def jump(nums: list[int]) -> int:
    res = 0
    l = r = 0


    while r < len(nums) - 1:
        farthest = 0
        for i in range(l, r + 1):
            farthest = max(farthest, i + nums[i])
        l = r + 1
        r = farthest
        res += 1
    return res

Time complexity: O(n) Space complexity: O(1)