Jump Game — Greedy Furthest Reach
Track the furthest index reachable so far; if you ever fall behind the current index, the end cannot be reached.
Problem Statement
Given an array where nums[i] indicates maximum jump length from position i, determine if you can reach the last index.
Why This Problem Matters
- Highlights greedy reasoning over dynamic programming for linear-time solutions.
- Introduces the concept of maintaining a furthest reachable frontier.
- Serves as a stepping stone for Jump Game II (minimum jumps).
Thought Process
Maintain furthest reach
Variable reach stores the furthest index reachable so far. As long as i <= reach, the position is accessible.
Update reach greedily
At each index, reach = max(reach, i + nums[i]). If reach ever exceeds or equals last index, you can stop early.
Detect failure immediately
If i ever surpasses reach, there is a gap you cannot cross so return false.
Step-by-Step Reasoning
- Initialise reach = 0.
- Iterate i from 0 to nums.length - 1 while i <= reach.
- Update reach = Math.max(reach, i + nums[i]).
- Return true if reach >= nums.length - 1; otherwise false after loop.
Dry Run
nums = [2,3,1,1,4]
reach progresses to 4 by index 1; return true.
nums = [3,2,1,0,4]
reach stops at index 3; i becomes 4 > reach so return false.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Single pass with constant additional variables.
Annotated Solution
public class JumpGame {
public boolean canJump(int[] nums) {
int reach = 0;
for (int i = 0; i < nums.length; i += 1) {
if (i > reach) {
return false;
}
reach = Math.max(reach, i + nums[i]);
if (reach >= nums.length - 1) {
return true;
}
}
return true;
}
}The greedy invariant is that every index up to reach is reachable. Once an index exceeds reach, the traversal fails.
Common Pitfalls
- Iterating past reach leads to array index errors; guard loop condition.
- Incorrectly comparing with > instead of >= when checking success misses cases where last index is exactly reachable.
- Misinterpreting nums[i] as steps remaining instead of maximum reach causes wrong updates.
Follow-Up Questions
- How do you compute the minimum number of jumps? (Use greedy BFS-level traversal or DP.)
- Can you return the path of indices used to reach the end?