Jump Game II
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.
A related problem, Jump Game (LeetCode 55), only asks whether we can reach the end. Here we need the minimum number of jumps, which turns a reachability question into an optimization question.
This problem 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 the answer is 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 is around 100 million operations, which is borderline. An O(n) approach is comfortably within limits.0 <= nums[i] <= 1000→ Jump values are non-negative, so we only move forward and never need to backtrack. This is what makes a greedy approach valid.- It's guaranteed that you can reach
nums[n - 1]→ We never have to handle the unreachable case, so no path-exists check is needed.
Approach 1: Dynamic Programming
Intuition
Define dp[i] as the minimum number of jumps to reach index i. We start at index 0, so dp[0] = 0. 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 the same idea as finding shortest paths in a DAG. Each index is a node, and there is 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
- Create an array
dpof sizen, initialized to a large value (infinity). - Set
dp[0] = 0since we start at index 0. - For each index
ifrom 1 ton - 1: - For each index
jfrom 0 toi - 1: - If
j + nums[j] >= i, updatedp[i] = min(dp[i], dp[j] + 1). - Return
dp[n - 1].
Example Walkthrough
Code
- Time Complexity: O(n^2). For each index
i, we check all previous indicesjfrom 0 toi-1. In the worst case, this is n(n-1)/2 comparisons. - Space Complexity: O(n). We store the
dparray of size n.
This is correct but O(n^2). The next approach drops the inner loop by changing the question from "which earlier index can reach me?" to "from the current jump range, what is the farthest I can reach with one more jump?"
Approach 2: BFS / Greedy
Intuition
Treat the array as a graph and run BFS on it. From index 0, we can reach indices 1 through nums[0] in one jump. That is level 1. From every index in level 1, we can reach a wider range in two jumps, which is level 2. Each BFS level is one jump, and the first level whose range includes the last index gives the answer.
BFS finds shortest paths in unweighted graphs. Each jump costs 1, so the first time the last index falls inside a level is the minimum number of jumps.
We do not need an actual queue. A level is a contiguous range of indices [currentStart, currentEnd], and the next level runs from currentEnd + 1 to the farthest index reachable from the current level. Two variables track this: currentEnd and farthest.
Level k is the set of indices reachable in at most k jumps. It always forms a prefix range [0, R_k]. The reason: an index j reachable in k jumps comes from some earlier index c with c + nums[c] >= j, and that same c can reach every index in [c+1, c+nums[c]], a contiguous block. Taking the union over all indices reachable in k-1 jumps (itself a prefix [0, R_{k-1}]) gives the prefix [0, R_k] where R_k is the maximum c + nums[c] over c <= R_{k-1}. That maximum is what farthest computes, which is why two variables replace a full queue.
Algorithm
- Initialize
jumps = 0,currentEnd = 0, andfarthest = 0. - 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
ireachescurrentEnd(we've explored the entire current BFS level): - Increment
jumpsby 1. - Set
currentEnd = farthest(move to the next BFS level). - If
currentEnd >= n - 1, we can stop early. - Return
jumps.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array exactly once, doing O(1) work at each index.
- Space Complexity: O(1). We only use three integer variables regardless of input size.