Jump Game II

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

• 0 <= j <= nums[i]
• 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].

Examples

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

Example 3:

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

Constraints

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1]

Approach

Key Insight

Greedy approach provides optimal solution!

The key is to think of the problem as selecting jump ranges rather than individual jumps.

• Track the farthest position reachable in the current jump range
• When you reach the end of the current range, you must make a jump
• The next range extends to the farthest position you could reach

Greedy Solution (Optimal)

Use a BFS-like greedy approach to track jump ranges.

Algorithm:

1. Initialize:

   • jumps = 0 (number of jumps made)
   • currentEnd = 0 (end of current jump range)
   • farthest = 0 (farthest reachable position)

2. For each position i from 0 to n-2:

   • Update farthest = max(farthest, i + nums[i])
   • If i == currentEnd (reached end of current range):
     • Increment jumps
     • Set currentEnd = farthest (start new range)

3. Return jumps

Why This Works:

• We're essentially doing BFS where each "level" is a jump
• We explore all positions reachable in the current jump
• When we've explored all positions in current jump, we move to next level

Key Optimization:

• We don't need to process the last index (we're already there)
• We only update farthest and make jumps when necessary

Alternative: Dynamic Programming

Bottom-up DP approach (less efficient).

Algorithm:

1. Create dp array: dp[i] = minimum jumps to reach index i
2. Initialize dp[0] = 0
3. For each position i:
   • For each position j that can jump to i:
     • dp[i] = min(dp[i], dp[j] + 1)
4. Return dp[n-1]

Complexity Analysis

Greedy Solution:

• Time Complexity: O(n) - single pass through array
• Space Complexity: O(1) - only constant extra space

DP Solution:

• Time Complexity: O(n²) - nested loops
• Space Complexity: O(n) - DP array

Pattern Recognition

This problem demonstrates:

• Greedy optimization for minimum jumps
• Range-based thinking (BFS-like approach)
• Jump range tracking pattern
• Extension of Jump Game I
• Common follow-up interview question

Related Problems

• Jump Game (prerequisite)
• Jump Game III
• Minimum Number of Taps to Open to Water a Garden
• Video Stitching