Definition
- Jump Game – a reachability problem where each array index allows a jump of up to its value, and we must determine whether the last index is reachable from the first.
- Greedy frontier – a single variable tracks the farthest index reachable so far, updated as
max(reach, i + nums[i])at each step. - Stuck condition – if the current index
iexceeds the farthest reach, there is no way to have arrived ati, so we returnfalse. - Monotone reachability – once a stretch of indices is reachable, only the farthest frontier matters going forward.
- Complexity – O(n) time for one scan and O(1) space for one integer variable.
At the National Bank of India, a multi-leg fund transfer passes through intermediary accounts, and each account can forward the funds up to a certain number of legs ahead based on its clearing limit. Rajesh checks whether the funds can reach the final settlement account by walking the chain and tracking the farthest account reachable so far.
Understanding the Concepts
What is the Jump Game problem?
Jump Game gives you an array of non-negative integers where each value represents the maximum number of positions you can jump forward from that index. Starting at index zero, you must determine whether you can reach the last index. This is a reachability problem that can be solved optimally with a greedy approach.
package com.bank.service;
public class JumpGame {
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]);
if (farthest >= nums.length - 1) return true;
}
return true;
}
}
Why does the greedy approach work?
The greedy works because reachability is monotone. If you can reach index i, you can reach every index from zero to i. This means the entire history of how you got to any index collapses into a single number: the farthest index reachable so far. You never need to remember which exact path was taken, only how far you can currently get.
package com.bank.service;
public class MonotoneReachability {
public static void main(String[] args) {
int[] nums = {2, 3, 1, 1, 4};
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
farthest = Math.max(farthest, i + nums[i]);
System.out.println("Index " + i + ": value=" + nums[i]
+ " farthest=" + farthest);
}
// Index 0: value=2 farthest=2
// Index 1: value=3 farthest=4 (reaches last index)
// Index 2: value=1 farthest=4
// Index 3: value=1 farthest=4
// Index 4: value=4 farthest=8
}
}
Index 0: value=2 farthest=2
Index 1: value=3 farthest=4
Index 2: value=1 farthest=4
Index 3: value=1 farthest=4
Index 4: value=4 farthest=8
How does the stuck condition work?
At each step, before extending the reach, we check whether the current index is even reachable. If i > farthest, it means no earlier index could have jumped to position i, so we are stranded. This check is the only way the algorithm returns false.
package com.bank.service;
public class StuckDemo {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 0, 4};
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) {
System.out.println("Stuck at index " + i
+ ": farthest was " + farthest);
return; // cannot reach last index
}
farthest = Math.max(farthest, i + nums[i]);
System.out.println("Index " + i + ": farthest=" + farthest);
}
}
}
Index 0: farthest=3
Index 1: farthest=3
Index 2: farthest=3
Index 3: farthest=3
Stuck at index 4: farthest was 3
What is the time and space complexity?
The algorithm performs a single left-to-right scan of the array, doing constant work at each index. It uses a single integer variable to track the farthest reach.
- Time complexity – O(n) for one pass through the array.
- Space complexity – O(1) because only one integer variable is used.
- Comparison – the equivalent DP approach uses a boolean array where
dp[i]marks whether indexiis reachable, costing O(n) space and O(n squared) time in the worst case.
// Greedy: O(n) time, O(1) space
int farthest = 0;
for (int i = 0; i < n; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
// DP alternative: 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; }
How is this different from Jump Game II (minimum jumps)?
Jump Game asks only whether the end is reachable (boolean answer), while Jump Game II asks for the minimum number of jumps to reach the end (integer answer). Jump Game II uses a BFS-like greedy that tracks the current jump boundary and counts layers.
| Aspect | Jump Game (I) | Jump Game II |
|---|---|---|
| Question | Can you reach the end? | Minimum jumps to reach end? |
| Answer type | Boolean | Integer |
| Strategy | Single farthest-reach variable | BFS-like layer counting |
| Variables | farthest | farthest, currentEnd, jumps |
| Complexity | O(n) time, O(1) space | O(n) time, O(1) space |
// Jump Game II: minimum jumps
public int jump(int[] nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
What are the edge cases?
Edge cases include a single-element array (already at the end, return true), an array starting with zero (stuck at the start unless it is the only element), and an array where every element is zero except the first.
package com.bank.service;
public class JumpEdgeCases {
public static void main(String[] args) {
JumpGame jg = new JumpGame();
// Single element: already at end
System.out.println(jg.canJump(new int[]{0})); // true
// Starts with zero, length > 1: stuck
System.out.println(jg.canJump(new int[]{0, 1})); // false
// All zeros except first
System.out.println(jg.canJump(new int[]{4, 0, 0, 0, 0})); // true
// Large jump at start
System.out.println(jg.canJump(new int[]{100, 0, 0})); // true
}
}
true
false
true
true
What are common mistakes?
The most frequent mistake is forgetting the stuck check before updating the reach. Without it, a zero-value index that should block progress gets silently passed. Another mistake is not handling the early termination when farthest already covers the last index.
// WRONG: no stuck check
for (int i = 0; i < n; i++) {
farthest = Math.max(farthest, i + nums[i]); // updates even if unreachable!
}
return farthest >= n - 1; // may report true incorrectly
// CORRECT: check before updating
for (int i = 0; i < n; i++) {
if (i > farthest) return false; // stuck check first
farthest = Math.max(farthest, i + nums[i]);
if (farthest >= n - 1) return true; // early exit
}
How would you apply this in a banking system?
At the National Bank of India, a chained fund transfer passes through intermediary accounts where each account can forward the funds a limited number of legs ahead based on its clearing limit. Before initiating the chain, the system checks whether the funds can reach the final settlement account.
package com.bank.service;
import java.util.List;
public class SettlementChainValidator {
public boolean canReachSettlement(List<Integer> clearingLimits) {
int farthest = 0;
for (int i = 0; i < clearingLimits.size(); i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + clearingLimits.get(i));
if (farthest >= clearingLimits.size() - 1) return true;
}
return true;
}
}
What should a senior engineer know?
A senior engineer should recognise that the greedy collapses an O(n squared) DP into O(n) by exploiting the monotone reachability property. They should also know that the greedy frontier is essentially a BFS frontier of size one, and that this pattern extends to other reachability problems. The key insight for interviews is: when reachability only grows, a single frontier variable captures the entire state.
// Senior insight: the greedy frontier is equivalent to
// maintaining a set of reachable indices, but because
// reachability is monotone (contiguous from 0), the set
// collapses to a single integer: the farthest index.
//
// This is why the greedy is correct and the DP is redundant.
Visual Overview
Array: [2] [3] [1] [1] [4] Index: 0 1 2 3 4 Step 0: i=0, value=2 farthest = max(0, 0+2) = 2 Reachable: [0 ──────── 2] Step 1: i=1, value=3 (1 <= 2, reachable) farthest = max(2, 1+3) = 4 Reachable: [0 ─────────────── 4] ← covers last index! Return true. Failing example: [3] [2] [1] [0] [4] Step 0: farthest = max(0, 0+3) = 3 Step 1: farthest = max(3, 1+2) = 3 Step 2: farthest = max(3, 2+1) = 3 Step 3: farthest = max(3, 3+0) = 3 ← stuck at 3 Step 4: i=4 > farthest=3 → STUCK → return false 0 1 2 3 4 ├─────┼─────┼─────┼─────┤ [===== reachable =====] X ← cannot reach
Key Takeaway
Jump Game asks whether I can reach the last index of an array when each index lets me jump up to its own value. The elegant solution is a greedy scan that tracks a single number: the farthest index I can currently reach. I walk left to right, and at each index I first check whether that index is even reachable by comparing it against the farthest reach. If an index lies beyond that reach, there is no way to have arrived, so I return false immediately.
Otherwise I extend the farthest reach to the maximum of its current value and the current index plus its jump value, and the moment that reach covers the last index I stop and return true. The reason the greedy is correct is that reachability is monotone: once a stretch of indices is reachable, the only thing that matters going forward is how far I can now get, which the single farthest-reach variable captures completely.
This runs in O(n) time and O(1) space, a major improvement over the quadratic DP that checks every pair of indices. A senior engineer recognises that the greedy frontier is essentially a BFS frontier that collapses to a single integer because reachability is contiguous from zero.
At the National Bank of India, I used this to validate a chained fund transfer across intermediary accounts, where each account could forward the funds a limited number of legs ahead based on its clearing limit. The system needed to know whether the funds could reach the final settlement account before initiating the chain.
Remember one sentence: track the farthest reachable index in one pass, and if you ever stand beyond it, you are stuck.
---