LeetCode 45: Jump Game II

Problem Description

LeetCode Problem 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. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• It’s guaranteed that you can reach nums[n - 1].

Difficulty: Medium

Tags: array, dynamic programming, greedy

Rating: 96.09%

Solution Approaches

Let’s explore two different approaches to solving this problem: Dynamic Programming and Greedy. Each has its own advantages and trade-offs.

1. Dynamic Programming Solution

The Dynamic Programming approach builds a solution by calculating the minimum jumps needed for each position.

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        
        # Initialize dp array with infinity except for starting position
        dp = [float('inf')] * n
        dp[0] = 0
        
        for i in range(n):
            # Try all possible jumps from current position
            for j in range(1, nums[i] + 1):
                if i + j >= n: break
                dp[i + j] = min(dp[i + j], 1 + dp[i])
        
        return dp[n - 1]

How the DP Solution Works

1. We create a DP array where dp[i] represents the minimum jumps needed to reach position i
2. Initially, all positions are set to infinity except dp[0] = 0
3. For each position i:
   • We explore all possible jumps (1 to nums[i])
   • For each reachable position, we update the minimum jumps needed
4. The final answer is stored in dp[n-1]

Time Complexity: $O(n²)$ - For each position, we might need to check all possible jumps

Space Complexity: $O(n)$ - We need an array of size n to store intermediate results

2. Greedy Solution

The Greedy approach is more efficient, maintaining two pointers to track the current and next maximum reach.

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1: return 0
            
        jumps = 0 
        current_max_reach = 0  # Furthest position reachable with current jumps
        next_max_reach = 0     # Furthest position reachable with one more jump
        
        for i in range(n - 1):
            # Update the furthest position we can reach with one more jump
            next_max_reach = max(next_max_reach, i + nums[i])
            
            # If we've reached the current maximum, we must jump
            if i == current_max_reach:
                jumps += 1
                current_max_reach = next_max_reach
                
                # Early exit if we can reach the end
                if current_max_reach >= n - 1:
                    break
        
        return jumps

How the Greedy Solution Works

1. We maintain two key variables:
   • current_max_reach: The furthest index we can reach with current number of jumps
   • next_max_reach: The furthest index we can reach with one more jump
2. As we iterate through the array:
   • We continuously update next_max_reach
   • When we reach current_max_reach, we must make a jump
   • After jumping, we update current_max_reach to next_max_reach
3. We can exit early if we can already reach the end

Time Complexity: $O(n)$ - We only need to traverse the array once

Space Complexity: $O(1)$ - We only use a constant amount of extra space

Key Insights

1. Greedy vs DP Trade-off: While the DP solution is more intuitive and easier to understand, the Greedy approach is significantly more efficient with O(n) time complexity.

2. Early Termination: Both solutions can benefit from early termination when we can already reach the end of the array.

3. Problem Guarantee: The problem’s guarantee that the end is always reachable simplifies our solutions as we don’t need to handle impossible cases.

Interview Tips

When solving this problem in an interview:

1. Start by explaining the simpler DP solution to demonstrate your understanding of the problem
2. Then optimize to the Greedy solution, explaining the intuition behind the optimization
3. Discuss the trade-offs between the two approaches
4. Remember to handle edge cases (array of length 1)
5. Consider mentioning possible follow-up questions like:
   • What if the end isn’t always reachable?
   • What if we want to return the actual path taken?