DSA-142 · FOCUSED PRACTICE
Jump Game II — Minimum Jumps
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 87395 deterministic checks. Learner drafts are not executed.
Understand the problem
Starting at index zero, a jump from i may land at any later index through i+nums[i]. Return the minimum number of jumps to the final index, or −1 if no such route exists.
- nums is a non-null int[] with length 0..100000 and nonnegative signed-int entries. Null throws NullPointerException; negative entries or excessive length throw IllegalArgumentException. Validate all entries before any early success or failure.
- Empty input has no starting position and returns −1. A singleton needs zero jumps, including [0]. Movement permits any positive distance up to the current value, never backward or exact-distance-only movement.
- Return only the optimal count, preserving the array. Unreachable inputs return −1 rather than relying on a reachability promise. Compute index+value in long, cap it to n−1, and only then narrow to int.
Examples
Input:
nums=[2,3,1,1,4]
Output:2The route 0→1→4 uses two jumps; the first jump cannot reach index four.
Input:
nums=[3,2,1,0,4]
Output:-1Every possible route remains inside indices zero through three.
Input:
nums=[0]
Output:0The starting index is already the destination.
Before you start
- Jump Game reachability and at-most movement semantics
- Breadth-first layers as minimum edge counts
Recognize the structure
Each reachable index contributes a complete interval of landing positions. Therefore all positions reachable with at most k jumps form a prefix [0,R(k)]. Scan the newly available layer to compute the next boundary without putting every outgoing edge into a queue. This is breadth-first minimum distance compressed by interval structure, rather than a rule that chooses the largest current array entry or the farthest immediate landing.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 96/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which indices can be reached with at most k jumps?
Hint 2
Can their union be summarized by a contiguous frontier?
Hint 3
Scan a complete frontier, accumulate the next reach, then count exactly one additional jump.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Relax every forward edge in index order
Keep a shortest-distance array with index zero at distance zero and n as an unreachable sentinel. For each reached index, inspect every legal later landing and minimize its distance. Increasing indices are a topological order of this forward-only graph. This O(n²)-time, O(n)-space baseline makes the shortest-path objective explicit and checks small tests; the test oracle instead computes reverse distances from the destination. Neither baseline nor oracle is run quadratically on the 100000-position stress cases.
Improve the baseline
Separate a layer boundary from its next reach
end is the farthest index reachable in the current jump budget; farthest accumulates all outgoing reach from positions scanned so far. jumps is that current budget. Initially end=farthest=0 and jumps=0. Scanning index zero discovers the one-jump layer, but no count is charged until its whole current layer is consumed.
Inspect every position in the current layer
Update farthest with min(n−1,index+nums[index]). An earlier position in the layer can reach farther than the rightmost position, so do not simply jump to end and read only its value. For [2,3,0,0,0], index one must be inspected even though the first frontier ends at two.
Charge one jump when a frontier is exhausted
At index==end, all sources available within the current budget have been inspected. If farthest==end, no new position can be reached and the destination is still beyond this frontier. Return −1. Otherwise increment jumps, assign end=farthest, and return that count when end reaches n−1.
Exclude the destination from source processing
The source scan stops at n−2. A singleton therefore executes no iteration and returns zero. Processing the destination as another source would charge a useless extra jump. Early return upon discovering a complete destination layer is safe because all earlier layers have already been exhausted.
Protect the arithmetic before narrowing
Even a tiny input may contain Integer.MAX_VALUE. Cast the index before addition; widening an already-overflowed int is too late. Capping the mathematical reach to the last index keeps both frontier variables in range and makes the equality success test exact.
Why it is correct
Prefix reachability
If all positions through R are reachable within k jumps, each scanned reachable source adds all intermediate landings through its own reach. Their union extends that same prefix without gaps. This property depends on permitting shorter jumps.
Layer optimality
After processing the sources through R(k), the accumulated farthest is exactly R(k+1). Every route of k+1 jumps ends in one of those outgoing intervals, and every such endpoint has a route of at most k+1 jumps. The first layer covering the destination consequently gives the minimum number of jumps.
Failure and termination
If the frontier cannot grow before covering the destination, no outgoing edge from any reachable source crosses it, so no future index can rescue the route. Otherwise end strictly increases at each boundary. The finite increasing scan cannot process an unreachable index because growth failure returns immediately. Input remains unchanged.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] nums) {
Objects.requireNonNull(nums, "nums");
if (nums.length > 100_000) throw new IllegalArgumentException("too many positions");
for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump");
}
public static int jump(int[] nums) {
validate(nums);
if (nums.length == 0) return -1;
int end = 0, farthest = 0, jumps = 0;
for (int index = 0; index < nums.length - 1; index++) {
farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index]));
if (index == end) {
if (farthest == end) return -1;
jumps++;
end = farthest;
if (end == nums.length - 1) return jumps;
}
}
return jumps;
}
// Quadratic shortest-distance baseline; short inputs only.
public static int baseline(int[] nums) {
validate(nums);
if (nums.length == 0) return -1;
int[] distance = new int[nums.length];
Arrays.fill(distance, nums.length);
distance[0] = 0;
for (int index = 0; index < nums.length; index++) {
if (distance[index] == nums.length) continue;
for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) {
distance[next] = Math.min(distance[next], distance[index] + 1);
}
}
return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1];
}
}
Read the meaningful blocks
Validate before a quick answer
The full value scan rejects [MAX_VALUE,−1] rather than returning success before noticing a malformed trailing entry. Empty input is handled before the n−1 source loop.
Accumulate reach before testing the boundary
The rightmost source itself contributes to the next layer, so its reach must be included before checking index==end. farthest is monotone and includes previous layers; older reaches cannot exceed the already finalized current boundary.
Return immediately after the first complete layer
Updating the count only at boundaries matches edge counts rather than visited-position counts. No route array, distance table, queue, or mutation is needed for a count-only result.
Complexity
Validation and the frontier scan take O(n) time, with O(1) auxiliary space and a scalar result. Each index is inspected at most once. Long addition is fixed-width and safe because the largest operand is a valid int plus an index below 100000.
The distance baseline uses O(n²) worst-case time and O(n) auxiliary space. A teaching trace may retain complete snapshots and layer descriptions; these are not allocations made by the constant-space reference.
Exact-state walkthroughs
Reveal normal and boundary traces
A whole first layer chooses the stronger interior source
Input: [2,3,0,0,0] · Minimum jumps / −1: 2
Step 1 of 8: Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
Phase: initial.
Completed budget: 0 jumps. Current frontier end: 0. Accumulated next reach: 0.
- 0: jump ≤ 2zero-jump starting position
- 1: jump ≤ 3beyond discovered reach
- 2: jump ≤ 0beyond discovered reach
- 3: jump ≤ 0beyond discovered reach
- 4: jump ≤ 0beyond discovered reach
Finalized at-most-jump boundaries — teaching history
- 0 jumps: [0,0]
Every permitted jump may be shortened, so each budget reaches a contiguous prefix. Count one jump only after scanning the whole current layer. Source processing stops before the destination.
| Variable | Value |
|---|---|
| input | [2,3,0,0,0] |
| phase | "initial" |
| end | 0 |
| farthest | 0 |
| jumps | 0 |
| layers | [0] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length > 100_000) throw new IllegalArgumentException("too many positions"); 9 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump"); 10 } 11 public static int jump(int[] nums) { 12 validate(nums); 13 if (nums.length == 0) return -1; 14 int end = 0, farthest = 0, jumps = 0; 15 for (int index = 0; index < nums.length - 1; index++) { 16 farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index])); 17 if (index == end) { 18 if (farthest == end) return -1; 19 jumps++; 20 end = farthest; 21 if (end == nums.length - 1) return jumps; 22 } 23 } 24 return jumps; 25 } 26 // Quadratic shortest-distance baseline; short inputs only. 27 public static int baseline(int[] nums) { 28 validate(nums); 29 if (nums.length == 0) return -1; 30 int[] distance = new int[nums.length]; 31 Arrays.fill(distance, nums.length); 32 distance[0] = 0; 33 for (int index = 0; index < nums.length; index++) { 34 if (distance[index] == nums.length) continue; 35 for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) { 36 distance[next] = Math.min(distance[next], distance[index] + 1); 37 } 38 } 39 return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1]; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
- input
[2,3,0,0,0]- phase
"initial"- end
0- farthest
0- jumps
0- layers
[0]
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[2,3,0,0,0]- phase
"scan"- end
0- farthest
2- jumps
0- layers
[0]- index
0- reach
2- previousFarthest
0
- Finish a layer and charge one jump.
This is exactly the next at-most-jump reachable prefix. The first layer covering the destination is minimum.
- input
[2,3,0,0,0]- phase
"layer"- end
2- farthest
2- jumps
1- layers
[0,2]- index
0
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[2,3,0,0,0]- phase
"scan"- end
2- farthest
4- jumps
1- layers
[0,2]- index
1- reach
4- previousFarthest
2
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[2,3,0,0,0]- phase
"scan"- end
2- farthest
4- jumps
1- layers
[0,2]- index
2- reach
2- previousFarthest
4
- Finish a layer and charge one jump.
This is exactly the next at-most-jump reachable prefix. The first layer covering the destination is minimum.
- input
[2,3,0,0,0]- phase
"layer"- end
4- farthest
4- jumps
2- layers
[0,2,4]- index
2
- Return the first complete layer count, or explicit failure.
The destination is never processed as another source. The source array remains unchanged.
- input
[2,3,0,0,0]- phase
"complete"- end
4- farthest
4- jumps
2- layers
[0,2,4]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
2
A stalled frontier cannot reach the last index
Input: [3,2,1,0,4] · Minimum jumps / −1: -1
Step 1 of 9: Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
Phase: initial.
Completed budget: 0 jumps. Current frontier end: 0. Accumulated next reach: 0.
- 0: jump ≤ 3zero-jump starting position
- 1: jump ≤ 2beyond discovered reach
- 2: jump ≤ 1beyond discovered reach
- 3: jump ≤ 0beyond discovered reach
- 4: jump ≤ 4beyond discovered reach
Finalized at-most-jump boundaries — teaching history
- 0 jumps: [0,0]
Every permitted jump may be shortened, so each budget reaches a contiguous prefix. Count one jump only after scanning the whole current layer. Source processing stops before the destination.
| Variable | Value |
|---|---|
| input | [3,2,1,0,4] |
| phase | "initial" |
| end | 0 |
| farthest | 0 |
| jumps | 0 |
| layers | [0] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length > 100_000) throw new IllegalArgumentException("too many positions"); 9 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump"); 10 } 11 public static int jump(int[] nums) { 12 validate(nums); 13 if (nums.length == 0) return -1; 14 int end = 0, farthest = 0, jumps = 0; 15 for (int index = 0; index < nums.length - 1; index++) { 16 farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index])); 17 if (index == end) { 18 if (farthest == end) return -1; 19 jumps++; 20 end = farthest; 21 if (end == nums.length - 1) return jumps; 22 } 23 } 24 return jumps; 25 } 26 // Quadratic shortest-distance baseline; short inputs only. 27 public static int baseline(int[] nums) { 28 validate(nums); 29 if (nums.length == 0) return -1; 30 int[] distance = new int[nums.length]; 31 Arrays.fill(distance, nums.length); 32 distance[0] = 0; 33 for (int index = 0; index < nums.length; index++) { 34 if (distance[index] == nums.length) continue; 35 for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) { 36 distance[next] = Math.min(distance[next], distance[index] + 1); 37 } 38 } 39 return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1]; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
- input
[3,2,1,0,4]- phase
"initial"- end
0- farthest
0- jumps
0- layers
[0]
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[3,2,1,0,4]- phase
"scan"- end
0- farthest
3- jumps
0- layers
[0]- index
0- reach
3- previousFarthest
0
- Finish a layer and charge one jump.
This is exactly the next at-most-jump reachable prefix. The first layer covering the destination is minimum.
- input
[3,2,1,0,4]- phase
"layer"- end
3- farthest
3- jumps
1- layers
[0,3]- index
0
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[3,2,1,0,4]- phase
"scan"- end
3- farthest
3- jumps
1- layers
[0,3]- index
1- reach
3- previousFarthest
3
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[3,2,1,0,4]- phase
"scan"- end
3- farthest
3- jumps
1- layers
[0,3]- index
2- reach
3- previousFarthest
3
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[3,2,1,0,4]- phase
"scan"- end
3- farthest
3- jumps
1- layers
[0,3]- index
3- reach
3- previousFarthest
3
- No edge leaves the reachable prefix.
The destination lies beyond end. No unreachable later position can extend this frontier.
- input
[3,2,1,0,4]- phase
"stalled"- end
3- farthest
3- jumps
1- layers
[0,3]- index
3
- Return the first complete layer count, or explicit failure.
The destination is never processed as another source. The source array remains unchanged.
- input
[3,2,1,0,4]- phase
"complete"- end
3- farthest
3- jumps
1- layers
[0,3]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
-1
Already at the destination
Input: [0] · Minimum jumps / −1: 0
Step 1 of 3: Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
Phase: initial.
Completed budget: 0 jumps. Current frontier end: 0. Accumulated next reach: 0.
- 0: jump ≤ 0zero-jump starting position
Finalized at-most-jump boundaries — teaching history
- 0 jumps: [0,0]
The singleton destination needs zero jumps. Source processing stops before the destination.
| Variable | Value |
|---|---|
| input | [0] |
| phase | "initial" |
| end | 0 |
| farthest | 0 |
| jumps | 0 |
| layers | [0] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length > 100_000) throw new IllegalArgumentException("too many positions"); 9 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump"); 10 } 11 public static int jump(int[] nums) { 12 validate(nums); 13 if (nums.length == 0) return -1; 14 int end = 0, farthest = 0, jumps = 0; 15 for (int index = 0; index < nums.length - 1; index++) { 16 farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index])); 17 if (index == end) { 18 if (farthest == end) return -1; 19 jumps++; 20 end = farthest; 21 if (end == nums.length - 1) return jumps; 22 } 23 } 24 return jumps; 25 } 26 // Quadratic shortest-distance baseline; short inputs only. 27 public static int baseline(int[] nums) { 28 validate(nums); 29 if (nums.length == 0) return -1; 30 int[] distance = new int[nums.length]; 31 Arrays.fill(distance, nums.length); 32 distance[0] = 0; 33 for (int index = 0; index < nums.length; index++) { 34 if (distance[index] == nums.length) continue; 35 for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) { 36 distance[next] = Math.min(distance[next], distance[index] + 1); 37 } 38 } 39 return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1]; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
- input
[0]- phase
"initial"- end
0- farthest
0- jumps
0- layers
[0]
- Return the first complete layer count, or explicit failure.
The destination is never processed as another source. The source array remains unchanged.
- input
[0]- phase
"complete"- end
0- farthest
0- jumps
0- layers
[0]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
0
No starting position
Input: [] · Minimum jumps / −1: -1
Step 1 of 3: No starting position exists; the frontier variables remain unused.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
Phase: initial.
No starting position or reachable frontier exists. The initialized scalar frontier variables are unused.
Finalized at-most-jump boundaries — teaching history
Empty.
Empty input has no starting position and returns −1. Source processing stops before the destination.
| Variable | Value |
|---|---|
| input | [] |
| phase | "initial" |
| end | 0 |
| farthest | 0 |
| jumps | 0 |
| layers | [] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length > 100_000) throw new IllegalArgumentException("too many positions"); 9 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump"); 10 } 11 public static int jump(int[] nums) { 12 validate(nums); 13 if (nums.length == 0) return -1; 14 int end = 0, farthest = 0, jumps = 0; 15 for (int index = 0; index < nums.length - 1; index++) { 16 farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index])); 17 if (index == end) { 18 if (farthest == end) return -1; 19 jumps++; 20 end = farthest; 21 if (end == nums.length - 1) return jumps; 22 } 23 } 24 return jumps; 25 } 26 // Quadratic shortest-distance baseline; short inputs only. 27 public static int baseline(int[] nums) { 28 validate(nums); 29 if (nums.length == 0) return -1; 30 int[] distance = new int[nums.length]; 31 Arrays.fill(distance, nums.length); 32 distance[0] = 0; 33 for (int index = 0; index < nums.length; index++) { 34 if (distance[index] == nums.length) continue; 35 for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) { 36 distance[next] = Math.min(distance[next], distance[index] + 1); 37 } 38 } 39 return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1]; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- No starting position exists; the frontier variables remain unused.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
- input
[]- phase
"initial"- end
0- farthest
0- jumps
0- layers
[]
- Return the first complete layer count, or explicit failure.
The destination is never processed as another source. The source array remains unchanged.
- input
[]- phase
"complete"- end
0- farthest
0- jumps
0- layers
[]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
-1
A full-width jump must not overflow
Input: [1,2147483647,0] · Minimum jumps / −1: 2
Step 1 of 7: Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
Phase: initial.
Completed budget: 0 jumps. Current frontier end: 0. Accumulated next reach: 0.
- 0: jump ≤ 1zero-jump starting position
- 1: jump ≤ 2147483647beyond discovered reach
- 2: jump ≤ 0beyond discovered reach
Finalized at-most-jump boundaries — teaching history
- 0 jumps: [0,0]
Every permitted jump may be shortened, so each budget reaches a contiguous prefix. Count one jump only after scanning the whole current layer. Source processing stops before the destination.
| Variable | Value |
|---|---|
| input | [1,2147483647,0] |
| phase | "initial" |
| end | 0 |
| farthest | 0 |
| jumps | 0 |
| layers | [0] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length > 100_000) throw new IllegalArgumentException("too many positions"); 9 for (int value : nums) if (value < 0) throw new IllegalArgumentException("negative jump"); 10 } 11 public static int jump(int[] nums) { 12 validate(nums); 13 if (nums.length == 0) return -1; 14 int end = 0, farthest = 0, jumps = 0; 15 for (int index = 0; index < nums.length - 1; index++) { 16 farthest = (int) Math.max(farthest, Math.min(nums.length - 1L, (long) index + nums[index])); 17 if (index == end) { 18 if (farthest == end) return -1; 19 jumps++; 20 end = farthest; 21 if (end == nums.length - 1) return jumps; 22 } 23 } 24 return jumps; 25 } 26 // Quadratic shortest-distance baseline; short inputs only. 27 public static int baseline(int[] nums) { 28 validate(nums); 29 if (nums.length == 0) return -1; 30 int[] distance = new int[nums.length]; 31 Arrays.fill(distance, nums.length); 32 distance[0] = 0; 33 for (int index = 0; index < nums.length; index++) { 34 if (distance[index] == nums.length) continue; 35 for (int next = index + 1; next < nums.length && next <= (long) index + nums[index]; next++) { 36 distance[next] = Math.min(distance[next], distance[index] + 1); 37 } 38 } 39 return distance[nums.length - 1] == nums.length ? -1 : distance[nums.length - 1]; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the zero-jump frontier at index zero.
Every distance up to the jump bound is allowed. Empty input has no start; a singleton already reaches the destination. Layer history is explanatory.
- input
[1,2147483647,0]- phase
"initial"- end
0- farthest
0- jumps
0- layers
[0]
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[1,2147483647,0]- phase
"scan"- end
0- farthest
1- jumps
0- layers
[0]- index
0- reach
1- previousFarthest
0
- Finish a layer and charge one jump.
This is exactly the next at-most-jump reachable prefix. The first layer covering the destination is minimum.
- input
[1,2147483647,0]- phase
"layer"- end
1- farthest
1- jumps
1- layers
[0,1]- index
0
- Include this reachable source in the next frontier.
end belongs to the current jump budget; farthest accumulates the next budget. All current-layer sources must contribute before a boundary is finalized.
- input
[1,2147483647,0]- phase
"scan"- end
1- farthest
2- jumps
1- layers
[0,1]- index
1- reach
2- previousFarthest
1
- Finish a layer and charge one jump.
This is exactly the next at-most-jump reachable prefix. The first layer covering the destination is minimum.
- input
[1,2147483647,0]- phase
"layer"- end
2- farthest
2- jumps
2- layers
[0,1,2]- index
1
- Return the first complete layer count, or explicit failure.
The destination is never processed as another source. The source array remains unchanged.
- input
[1,2147483647,0]- phase
"complete"- end
2- farthest
2- jumps
2- layers
[0,1,2]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
2
Test the contract
Input:
nums=[]
Output:-1There is no start.
Input:
nums=[1,1,1,1]
Output:3Every step advances one index.
Input:
nums=[2,3,0,0,0]
Output:2The useful second source is inside the first frontier.
Input:
nums=[0,1]
Output:-1No frontier growth.
Input:
nums=[1,2147483647,0]
Output:2Widened reach calculation.
Input:
nums=[2,-1,0]
Output:IllegalArgumentExceptionValidation precedes early reachability success.
Common mistakes and counterexamples
Pick the farthest immediate landing
Counterexample: [2,3,0,0,0] gets stuck at two, while 0→1→4 succeeds.
Inspect all sources of a BFS layer before finalizing its next reach.
Count every scanned index as a jump
Counterexample: [3,0,0,0] needs one jump despite three possible sources.
Increment only when the current layer boundary is exhausted.
Assume the destination is reachable
Counterexample: [0,1] cannot grow beyond zero.
Detect farthest==end at the boundary and return −1.
Add in int or process the last index
Counterexample: [1,MAX_VALUE,0] can overflow an uncast sum; [0] must not need one jump.
Widen before adding, cap reach, and scan only through n−2.
Follow-ups
Return an actual minimum-jump route.
Record a parent when an index first enters a new frontier; each newly discovered index is assigned once. Backtrack from the destination. This usually uses O(n) space, and tie rules should specify which minimum route to return.
Allow only the exact stated jump length.
Reachable sets may have holes, so a single farthest boundary loses essential information. Model actual edges and use visited states or the resulting deterministic successor graph; do not reuse the prefix proof.
Give jumps unequal costs.
BFS layers minimize edge count only for unit costs. With arbitrary nonnegative jump costs, use an appropriate shortest-path state and prove how edge costs are represented before compressing it.