MediumEditorial · 6 minGenerated by the editor · Sep 8
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Intuitionwhy the farthest reachable frontier is enough
You do not need to choose one exact jump at each position. What matters is the farthest index reachable using all positions you have already been able to land on. If that frontier reaches the last index, a valid sequence of jumps exists; if the next index lies beyond it, no earlier choice can reach that index either.
Scan from left to right and maintain maxReach, the farthest index reachable so far. At index i, first check whether i is inside the known reachable region. If it is, this position can extend the region to i + nums[i]. Keep the larger of the old and new frontiers, because a shorter jump from an earlier position must never erase a longer reach.
The scan needs only the farthest reachable boundary, not every individual path.
Approachmaintain one invariant while scanning once
1Set maxReach to 0, because index 0 is the starting position and is reachable before any jump is considered.
2Visit indices from left to right, because every index before the current one has already had a chance to extend the reachable frontier.
3If i is greater than maxReach, return false immediately, because the scan has reached a position that no earlier reachable index can land on.
4Update maxReach to the larger of maxReach and i + nums[i], because the current position may extend the frontier but must not shorten a reach found earlier.
5If maxReach reaches the last index, return true, because some chain of valid jumps has already reached or passed the destination.
6Return true after the loop, because every processed index was reachable and reaching the end of the scan means the last index was not blocked by an unreachable gap.
Complexityone pass and constant working memory
MEASURE
BOUND
WHY
Time
O(n)
The loop examines each array index at most once, and each visit performs a constant number of arithmetic and comparison operations, so no index causes repeated exploration.
Space
O(1) extra
Only maxReach and the loop index are stored; the input array is not copied, and there is no output structure whose storage needs to be counted. The bound stays constant even in the worst case where every value is large or every reachable jump is short.
CPPGreedy scan that returns as soon as the reachable frontier reaches the destination.
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxReach = 0;
for (int i = 0; i < static_cast<int>(nums.size()); i++) {
if (i > maxReach) return false;
maxReach = max(maxReach, i + nums[i]);
if (maxReach >= static_cast<int>(nums.size()) - 1) return true;
}
return true;
}
};
The unreachable check must come before using nums[i]. Once i is beyond maxReach, this position cannot contribute any jump, so extending the frontier from it would invent a path through a gap. The max operation is equally important: a position with a small jump must not reduce a farther frontier already obtained from an earlier index.
Common mistakestwo wrong shapes that look plausible on small tests