Definition
- Jump Game – a reachability problem where each array element represents the maximum jump length from that position, and we determine whether the last index is reachable from index zero.
- Greedy frontier – maintain a single integer
reachstarting at zero, updated asmax(reach, i + nums[i])at each step. - Stuck condition – if the current index
iexceedsreach, no earlier position could have jumped here, so we returnfalse. - Monotone property – reachability is contiguous from zero, so the entire reachable set collapses to one number.
- Complexity – O(n) time for a single pass and O(1) space for one variable.
At the National Bank of India, a settlement pipeline has stages, and each stage declares how many stages ahead it can skip based on its clearing capacity. Rajesh walks the pipeline tracking the farthest stage reachable so far. If he ever stands beyond that frontier, the pipeline cannot complete.
Understanding the Concepts
What is the Jump Game problem?
Jump Game gives you an array of non-negative integers where each value is the maximum forward jump from that index. Starting from index zero, determine whether you can reach the last index. The answer is a boolean: reachable or not.
package com.bank.service;
public class JumpGameReachability {
public boolean canReach(int[] nums) {
int reach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
if (reach >= nums.length - 1) return true;
}
return true;
}
}
Why does the greedy work?
The greedy works because reachability is monotone. If you can reach index i, you can also reach every index between zero and i. This means the full reachable set is always a contiguous range starting at zero, and a single integer, the farthest endpoint of that range, captures everything. You never need to remember which exact path got you to any index.
package com.bank.service;
public class ReachabilityMonotone {
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
int reach = 0;
for (int i = 0; i < nums.length; i++) {
reach = Math.max(reach, i + nums[i]);
System.out.println("i=" + i + " jump=" + nums[i]
+ " reach=" + reach);
}
// Output:
// i=0 jump=2 reach=2
// i=1 jump=3 reach=4
// i=2 jump=1 reach=4
// i=3 jump=1 reach=4
// i=4 jump=4 reach=8
}
}
i=0 jump=2 reach=2
i=1 jump=3 reach=4
i=2 jump=1 reach=4
i=3 jump=1 reach=4
i=4 jump=4 reach=8
How does the algorithm handle being stuck?
At each step, the algorithm checks whether the current index is within the reachable range. If i > reach, no earlier index could have jumped to i, and the algorithm returns false. This is the only condition that causes failure.
package com.bank.service;
public class StuckExample {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 0, 4};
int reach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reach) {
System.out.println("STUCK at index " + i);
return;
}
reach = Math.max(reach, i + nums[i]);
System.out.println("i=" + i + " reach=" + reach);
}
}
}
i=0 reach=3
i=1 reach=3
i=2 reach=3
i=3 reach=3
STUCK at index 4
How is this different from the DP approach?
The DP approach uses a boolean array where dp[i] marks whether index i is reachable. For each index, it checks all prior indices that could jump to it. This is O(n squared) time and O(n) space. The greedy collapses the entire boolean array into one integer.
| Aspect | Greedy | Dynamic Programming |
|---|---|---|
| State | Single integer reach | Boolean array dp[n] |
| Time | O(n) | O(n squared) |
| Space | O(1) | O(n) |
| Logic | Extend frontier | Check all prior jumpers |
// DP: O(n^2) time, O(n) space
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (dp[j] && j + nums[j] >= i) { dp[i] = true; break; }
return dp[n - 1];
// Greedy: O(n) time, O(1) space
int reach = 0;
for (int i = 0; i < n; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
What are the edge cases?
Several edge cases need attention: a single-element array is trivially reachable, an array starting with zero and length greater than one is stuck immediately, and a very large first element can cover the entire array in one jump.
package com.bank.service;
public class ReachEdgeCases {
public static void main(String[] args) {
JumpGameReachability jg = new JumpGameReachability();
System.out.println(jg.canReach(new int[]{0})); // true
System.out.println(jg.canReach(new int[]{0, 5})); // false
System.out.println(jg.canReach(new int[]{10, 0, 0, 0})); // true
System.out.println(jg.canReach(new int[]{1, 1, 1, 1})); // true
System.out.println(jg.canReach(new int[]{1, 0, 0})); // false
}
}
true
false
true
true
false
What are common mistakes?
The most common mistake is updating the reach without first checking whether the current index is reachable. This can cause the algorithm to report an unreachable array as reachable. Another mistake is forgetting to handle the single-element base case.
// WRONG: no stuck check
int reach = 0;
for (int i = 0; i < n; i++) {
reach = Math.max(reach, i + nums[i]);
}
return reach >= n - 1; // may incorrectly return true
// CORRECT: stuck check before update
int reach = 0;
for (int i = 0; i < n; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
How would you apply this in a banking system?
At the National Bank of India, a settlement pipeline has stages where each stage declares how many stages ahead it can skip based on its clearing capacity. Before initiating the pipeline, the system checks whether the final settlement stage is reachable from the first.
package com.bank.service;
import java.util.List;
public class PipelineReachabilityService {
public boolean canCompleteSettlement(List<Integer> stageLimits) {
int reach = 0;
for (int i = 0; i < stageLimits.size(); i++) {
if (i > reach) return false;
reach = Math.max(reach, i + stageLimits.get(i));
if (reach >= stageLimits.size() - 1) return true;
}
return true;
}
}
What should a senior engineer know?
A senior engineer should recognise that the greedy frontier is essentially a compressed BFS where the frontier is always a contiguous range. They should also know that this pattern generalises to any problem where reachability grows monotonically. The interview insight is: when the reachable set is contiguous, one integer replaces an entire boolean array.
// Senior insight: the greedy frontier = compressed BFS
// BFS would maintain a queue of reachable indices.
// Because reachability is contiguous [0..reach],
// the queue collapses to a single integer.
// This is why O(n^2) DP becomes O(n) greedy.
What are common interview follow-up questions?
Interviewers often follow up with these questions:
- What if you need the minimum number of jumps (Jump Game II)?
- What if some indices are forbidden (Jump Game III)?
- Can you solve it with backward greedy (start from the end)?
- What if the array can contain negative values?
// Backward greedy alternative:
// Start with lastGood = n-1
// Walk right to left: if i + nums[i] >= lastGood, set lastGood = i
// Return lastGood == 0
int lastGood = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastGood) lastGood = i;
}
return lastGood == 0;
Visual Overview
Array: [2] [3] [1] [1] [4] Index: 0 1 2 3 4 Scan left to right: ┌─────────────────────────────────────────┐ │ i=0: reach = max(0, 0+2) = 2 │ │ Reachable: [0────2] │ │ i=1: 1 <= 2 ✓ reach = max(2, 1+3) = 4 │ │ Reachable: [0────────────4] │ │ 4 >= 4 (last index) → return true │ └─────────────────────────────────────────┘ Failing: [3] [2] [1] [0] [4] ┌─────────────────────────────────────────┐ │ i=0: reach=3 i=1: reach=3 │ │ i=2: reach=3 i=3: reach=3 │ │ i=4: 4 > 3 → STUCK → return false │ └─────────────────────────────────────────┘ Forward greedy vs Backward greedy: Forward: track farthest reachable from left Backward: track last good position from right Both: O(n) time, O(1) space
Key Takeaway
Jump Game is a greedy reachability problem. I keep a single variable for the farthest index I can reach so far and walk the array left to right. At each index, if the index is already beyond my farthest reach, I could never have arrived there and I return false. Otherwise I extend the reach to the maximum of its current value and the index plus the jump available there.
The greedy is correct because reachability is monotone: if I can reach some index, I can reach everything up to my current frontier, so I never need to know which exact path got me there, only the single farthest point. If the walk completes without getting stranded, the last index is reachable. This runs in O(n) time and O(1) space, collapsing the quadratic DP into a single integer.
Edge cases include a single-element array (trivially true), an array starting with zero (immediate failure if length is greater than one), and arrays where the first element covers the entire range. The common mistake is updating the reach without first checking whether the current index is reachable.
At the National Bank of India, a settlement pipeline had stages where each stage declared how many stages ahead it could skip, and operations needed to know if the final stage was reachable from the start. The constant-space greedy frontier gave the answer in a single pass.
Remember one sentence: track the farthest reachable index, and if you ever stand beyond it, you are stuck.
---