Jump Game II | Leetcode 45

Welcome to Jump Game II (Leetcode 45). In the original Jump Game, we merely had to return a boolean indicating if the end was reachable. Now, we are guaranteed that the end is reachable, but we must return the minimum number of jumps required to get there.

Problem Statement

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 nums[n - 1]. The test cases are generated such that you can always reach nums[n - 1].

Example: nums = [2, 3, 1, 1, 4] => Output: 2 (Jump 1 step from index 0 to 1, then 3 steps to the last index).

Approach 1: 1D Dynamic Programming O(N^2)

A classic DP approach. We can construct a dp array where dp[i] represents the minimum number of jumps needed to reach index i from index 0.

We initialize all values in dp to infinity, except dp[0] = 0 (since it takes 0 jumps to be at the start). For every index i, we look at all previous indices j (where j < i). If index i can be reached from index j (j + nums[j] >= i), we update dp[i] to be the minimum of its current value and dp[j] + 1!

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        dp[0] = 0
        
        for i in range(1, n):
            # Check all previous platforms j to see if they can reach i
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j] + 1)
                    # We can break early here because the first j that reaches i
                    # is guaranteed to have the smallest number of jumps due to DP structure!
                    break 
                    
        return dp[-1]

Complexity Analysis

Approach 2: Implicit BFS (Greedy) O(N)

We can radically improve upon O(N^2) DP by using a Greedy approach that mimics an implicit Breadth-First-Search.

Instead of jumping specifically from index to index, we evaluate the array in ranges (or levels). For any given jump range [left, right], we can physically scan those elements to figure out the absolute farthest index we could possibly reach in our next jump.

Once our i pointer finishes scanning the current range (hits right), we unequivocally record 1 jump, update our left to be right + 1, and update our right to be farthest.

graph LR
    A["nums = [2, 3, 1, 1, 4]"]
    B["Jump 0: Range [0, 0]"]
    C["Jump 1: Range [1, 2]"]
    D["Jump 2: Range [3, 4]"]
    
    A --> B
    B -->|"Farthest from [0] is idx 2"| C
    C -->|"Farthest from [1,2] is idx 4"| D
    D -.->|"End Reached"| E((Returns 2))

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        left = 0
        right = 0
        farthest = 0
        
        # We stop at len(nums) - 1 because if right == len-1, 
        # we are already there and don't need to initiate another jump!
        for i in range(len(nums) - 1):
            # Continuously calculate the undisputed farthest reach from our current "window"
            farthest = max(farthest, i + nums[i])
            
            # When we finish sweeping the current window
            if i == right:
                jumps += 1
                left = right + 1  # Technically left pointer isn't explicitly uniquely needed
                right = farthest
                
        return jumps

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (45)