Core Idea
If we can stand on an index i, we can certainly stand on every index j < i, because we reached i by stepping through them. Therefore, to know whether the whole game is solvable it is enough to track the furthest index we can currently reach.
📌 Algorithm
Let reachable be the largest index known to be reachable so far.
Iterate once through the array:
- (1) for each position i, verify we can actually stand on it (i ≤ reachable). If not, the game is lost.
- (2) Otherwise ‑‑ update reachable with
i + nums[i]if that value is larger.
The moment reachable crosses n − 1, the last cell is reachable and we can stop early.
This greedy invariant guarantees optimality because we always carry forward the maximum horizon achievable so far.
Solution
class Solution {
public boolean canJump(int[] nums) {
int reachable = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reachable) return false;
reachable = Math.max(reachable, i + nums[i]);
if (reachable >= nums.length - 1) return true;
}
return true;
}
}
Time Complexity: O(N)
Space Complexity: O(1)
Implementation Notes
Do we need dynamic programming?
No. Because jumps are only forward and each position carries a single parameter (nums[i]), a greedy scan suffices.
Zero values are harmless if preceded by sufficient reach.
A 0 merely means we cannot jump from that index. As long as reachable already leaps over it, the path remains open.