45. Jump Game 2

Problem Statement in English

You’re given an array of non-negative integers nums, where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps.

Approach

There are 2 approaches to solve this problem: Dynamic Programming and Greedy.

Dynamic Programming Approach

In this approach we keep it simple. The number of jumps from the current index to the end is equal to 1 + the minimum number of jumps from the next reachable indices. We can use memoization to store the results of subproblems.

This approach has a time complexity of $O(n^2)$ and space complexity of $O(n)$.

Greedy Approach

This approach relies on the fact that we can keep track of the farthest index we can reach at each step. We only use a jump when we reach the end of the current jump range. By that time we would have already calculated the farthest index we can reach in the next jump.

This approach has a time complexity of $O(n)$ and space complexity of $O(1)$.

And we’re done!

Solution in Python

• 1D DP Approach

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

        @cache
        def dp(i):
            if i >= N - 1:
                return 0

            steps = inf

            for j in range(i + 1, min(N, i + nums[i] + 1)):
                steps = min(steps, dp(j))

            return 1 + steps

        return dp(0)

• Optimized Greedy Approach

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        current_end = 0
        farthest = 0

        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])

            if i == current_end:
                jumps += 1
                current_end = farthest

        return jumps

Mistakes I Made

I didn’t come up with the greedy approach by myself :(

And we are done.