AlgoMaster Logo

Jump Game II

Last Updated: March 29, 2026

medium
4 min read

Understanding the Problem

We start at index 0 and want to reach the last index using the fewest jumps possible. At each position i, we can jump forward by any amount from 1 to nums[i]. The problem guarantees a path exists, so we never need to worry about getting stuck.

This is different from Jump Game (LeetCode 55), which only asks whether we can reach the end. Here we need the minimum number of jumps, which changes the problem from a reachability question to an optimization question.

The key observation is that this has a BFS-like structure. From index 0, we can reach a "range" of indices in one jump. From that entire range, we can reach a wider range in two jumps. Each "level" of this BFS corresponds to one jump, and we want to find the level at which the last index first becomes reachable.

Key Constraints:

  • 1 <= nums.length <= 10^4 → With n up to 10,000, an O(n^2) approach (around 100 million operations) is borderline. O(n) is preferred.
  • 0 <= nums[i] <= 1000 → Jump values are non-negative, so we can only move forward. This makes the problem amenable to greedy approaches since we never need to backtrack.
  • It's guaranteed that you can reach nums[n - 1] → We don't need to handle the "impossible" case. This simplifies the logic because we know a valid path always exists.

Approach 1: Dynamic Programming

Intuition

The most straightforward approach is DP. Define dp[i] as the minimum number of jumps to reach index i. We know dp[0] = 0 because we start there. For every other index i, we look at all earlier indices j that can reach i (meaning j + nums[j] >= i) and take the minimum of dp[j] + 1.

This is essentially the same idea as finding shortest paths in a DAG. Each index is a node, and there's an edge from j to every index in the range [j+1, j+nums[j]]. We want the shortest path from node 0 to node n-1.

Algorithm

  1. Create an array dp of size n, initialized to a large value (infinity).
  2. Set dp[0] = 0 since we start at index 0.
  3. For each index i from 1 to n - 1:
    • For each index j from 0 to i - 1:
      • If j + nums[j] >= i, update dp[i] = min(dp[i], dp[j] + 1).
  4. Return dp[n - 1].

Example Walkthrough

1Input array: nums = [2, 3, 1, 1, 4]
0
2
1
3
2
1
3
1
4
4
1/6
1Initialize dp: dp[0]=0, rest = ∞
[0, ∞, ∞, ∞, ∞]
1/6

Code

This approach works correctly but is O(n^2). What if instead of asking "which earlier index can reach me?", we flipped the perspective and asked "from the current jump range, what's the farthest I can reach with one more jump?"

Approach 2: BFS / Greedy

Intuition

Here's the insight that transforms this problem: think of it as BFS on a graph. From index 0, we can reach indices 1 through nums[0] in one jump. That's "level 1" of our BFS. From every index in level 1, we can reach a wider range in two jumps. That's "level 2." Each BFS level is one jump, and the first time the last index falls within our reachable range, we have our answer.

This works because BFS naturally finds shortest paths in unweighted graphs. Each jump has a "cost" of 1, so the first time we reach the last index is guaranteed to be via the minimum number of jumps.

The beauty of this approach is that we don't need an actual queue. The "level" is just a contiguous range of indices [currentStart, currentEnd], and the next level spans from currentEnd + 1 to the farthest index reachable from the current level.

Algorithm

  1. Initialize jumps = 0, currentEnd = 0, and farthest = 0.
  2. Iterate through the array from index 0 to n - 2 (we don't need to process the last index):
    • Update farthest = max(farthest, i + nums[i]).
    • If i reaches currentEnd (we've explored the entire current BFS level):
      • Increment jumps by 1.
      • Set currentEnd = farthest (move to the next BFS level).
      • If currentEnd >= n - 1, we can stop early.
  3. Return jumps.

Example Walkthrough

1Initialize: jumps=0, currentEnd=0, farthest=0
0
currentEnd
2
i
1
3
2
1
3
1
4
4
1/5

Code