Definition
- Greedy layered BFS – treat each jump as expanding a range; each jump is one BFS level from the current window to the farthest reachable position.
- Current window boundary – the rightmost index reachable with the current number of jumps; when the index reaches this boundary, a new jump is needed.
- Farthest reachable – as we scan within the current window, track the maximum of
i + nums[i]to know how far the next jump can reach. - Iterate to n-2 – stop at the second-to-last index because reaching or passing the last index inside the final window already counts the jump.
- Time O(n), space O(1) – a single pass with three variables: jumps, end, farthest.
A courier at National Bank of India wants the fewest hops across settlement stages. Within one hop he can land anywhere in his current window. He scouts the entire window to find the farthest he could then reach, and only counts a new hop when he steps off the edge of his current window.
Understanding the Concepts
What is the Jump Game II problem?
The problem gives an array where each element represents the maximum jump length from that position. The task is to return the minimum number of jumps needed to reach the last index. It is guaranteed that the last index is reachable.
This can be modelled as a shortest-path problem where each index is a node and each index can reach the next nums[i] indices. BFS would give the minimum jumps, but we can optimise it to a greedy linear scan.
package com.bank.service;
public class JumpGameII {
public int jump(int[] nums) {
int jumps = 0;
int end = 0; // current window boundary
int farthest = 0; // farthest reachable from current window
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == end) {
jumps++;
end = farthest;
}
}
return jumps;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
System.out.println("Min jumps: " + new JumpGameII().jump(nums));
}
}
Min jumps: 2
Why does greedy give the minimum jumps?
The greedy approach is equivalent to BFS where each jump is one BFS level. Within a level (window), we find the farthest position reachable. Since we always extend to the maximum farthest, each level covers the widest possible range, which means we use the fewest levels (jumps). This is the optimal substructure: extending to the farthest each time cannot be beaten.
package com.bank.service;
public class GreedyBFSEquivalence {
// BFS level 0: index 0
// BFS level 1: indices 1..nums[0] (one jump)
// BFS level 2: indices (window end + 1)..farthest (two jumps)
// ...
// The greedy tracks these levels with just 3 variables.
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
System.out.println("Level 0: index 0");
System.out.println("Level 1: indices 1..2 (jump 1)");
System.out.println("Level 2: indices 3..4 (jump 2)");
System.out.println("Reached end at level 2 => 2 jumps.");
}
}
How does the window boundary work?
The variable end marks the rightmost index reachable with the current number of jumps. As we scan from left to right, we update farthest at each index. When i reaches end, we have exhausted the current window and must take a new jump. At that point, we increment jumps and move end to farthest.
package com.bank.service;
public class WindowBoundaryTrace {
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
int jumps = 0, end = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
System.out.println("i=" + i + " nums[i]=" + nums[i]
+ " farthest=" + farthest + " end=" + end);
if (i == end) {
jumps++;
end = farthest;
System.out.println(" => Jump! jumps=" + jumps + " new end=" + end);
}
}
System.out.println("Total jumps: " + jumps);
}
}
i=0 nums[i]=2 farthest=2 end=0
=> Jump! jumps=1 new end=2
i=1 nums[i]=3 farthest=4 end=2
i=2 nums[i]=1 farthest=4 end=2
=> Jump! jumps=2 new end=4
Total jumps: 2
Why iterate only to n-2?
We iterate to nums.length - 2 (the second-to-last index) because reaching or passing the last index inside the final window already counts the jump. If we iterated to the last index and i == end happened there, we would increment jumps one extra time, overcounting by one.
package com.bank.service;
public class WhyNMinus2 {
// Example: nums = [1, 1, 1]
// Correct: iterate i=0, i=1 (stop before i=2)
// i=0: farthest=1, i==end => jump=1, end=1
// i=1: farthest=2, i==end => jump=2, end=2
// Result: 2 jumps (correct)
//
// Wrong: iterate i=0, i=1, i=2
// i=2: farthest=3, i==end => jump=3 (WRONG, overcounted)
public static void main(String[] args) {
int[] nums = {1, 1, 1};
System.out.println("Correct (stop at n-2): 2 jumps");
System.out.println("Wrong (include n-1): 3 jumps (overcounted)");
}
}
How is this different from Jump Game I?
| Feature | Jump Game I | Jump Game II |
|---|---|---|
| Question | can you reach the end? | what is the minimum jumps to reach the end? |
| Return type | boolean | integer |
| Approach | track farthest reachable | greedy window + jump counter |
| When to stop | farthest >= last index | iterate to n-2 |
| Complexity | O(n) time, O(1) space | O(n) time, O(1) space |
package com.bank.service;
public class JumpGameIvsII {
// Jump Game I: can you reach the end?
public boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
System.out.println("Can reach: " + new JumpGameIvsII().canJump(nums));
System.out.println("Min jumps: " + new JumpGameII().jump(nums));
}
}
Can reach: true
Min jumps: 2
What are the edge cases?
Edge cases include an array of length 1 (already at the end, 0 jumps), an array where the first element can reach the end directly (1 jump), and an array where every element is 1 (need n-1 jumps).
package com.bank.service;
public class JumpGameEdgeCases {
public static void main(String[] args) {
JumpGameII solver = new JumpGameII();
System.out.println("Single element: " + solver.jump(new int[]{0})); // 0
System.out.println("Direct reach: " + solver.jump(new int[]{5, 1, 1, 1, 1})); // 1
System.out.println("All ones: " + solver.jump(new int[]{1, 1, 1, 1})); // 3
}
}
Single element: 0
Direct reach: 1
All ones: 3
What are common mistakes?
The most common mistake is iterating to the last index instead of n-2, which overcounts by one. Another mistake is not updating farthest before checking the window boundary, which misses the current index's contribution.
Wrong code:
// WRONG: iterates to n-1, overcounts
for (int i = 0; i < nums.length; i++) { // should be nums.length - 1
farthest = Math.max(farthest, i + nums[i]);
if (i == end) { jumps++; end = farthest; }
}
Correct code:
// CORRECT: stops at n-2
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == end) { jumps++; end = farthest; }
}
What should a senior engineer know?
A senior engineer connects this to BFS layer counting and recognises it as the greedy compression of a BFS. They know that the DP approach with dp[i] = min jumps to reach i is O(n squared) and the greedy is O(n) because it avoids recomputing ranges. At National Bank of India, the same window-expansion logic applies to routing settlement messages through relay stages with minimum hops.
package com.bank.service;
public class SeniorJumpNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" 1. Greedy is BFS compressed to 3 variables.");
System.out.println(" 2. DP approach is O(n^2), greedy is O(n).");
System.out.println(" 3. Iterate to n-2 to avoid overcounting.");
System.out.println(" 4. Same pattern: minimum relay hops in settlement.");
}
}
Visual Overview
Jump Game II: Greedy Window Expansion
nums = [2, 3, 1, 1, 4]
index: 0 1 2 3 4
Window 0 (start): [0]
┌───┐
│ 0 │ farthest = 0+2 = 2
└───┘
i == end => jump! jumps=1, end=2
Window 1 (jump 1): [1, 2]
┌───┬───┐
│ 1 │ 2 │ farthest = max(1+3, 2+1) = 4
└───┴───┘
i == end => jump! jumps=2, end=4
end=4 >= last index (4) => reached!
Result: 2 jumps
BFS equivalence:
Level 0: {0} 0 jumps
Level 1: {1, 2} 1 jump
Level 2: {3, 4} 2 jumps <-- 4 is the target
Key Takeaway
Jump Game II asks for the minimum number of jumps to reach the last index, and the optimal solution is a greedy window expansion that compresses a BFS into three variables. The current window boundary marks the rightmost index reachable with the current number of jumps. As we scan left to right, we track the farthest reachable index. When the scan position reaches the window boundary, we must take a new jump and move the boundary to the farthest.
The critical detail is iterating only to the second-to-last index. Reaching or passing the last index inside the final window already counts the jump, so including the last index in the loop would overcount by one. The time is O(n) and the space is O(1).
The greedy works because extending to the farthest reachable within each window is equivalent to BFS level processing, and BFS gives the shortest path in an unweighted graph. Each window is one BFS level, and because we always take the widest window, we use the fewest levels.
At National Bank of India, a courier crossed settlement stages and needed the fewest hops because each hop carried a fixed handling cost. The greedy window expansion gave the minimum hops in a single linear pass. The DP alternative with dp[i] = minimum jumps to reach i is O(n squared), which Rajesh avoided by recognising the BFS structure.
Remember one sentence: count a jump when the index hits the current window boundary, extend the boundary to the farthest reachable, and stop at n-2 to avoid overcounting.
---