Greedy Idea
Maintain maxReach = farthest index reachable so far. At each index i, if i > maxReach you're stuck. Otherwise update maxReach = max(maxReach, i + nums[i]).
Algorithm
maxReach = 0
for i = 0 to n-1:
if i > maxReach: // stuck
return false
maxReach = max(maxReach, i + nums[i])
return true
for i = 0 to n-1:
if i > maxReach: // stuck
return false
maxReach = max(maxReach, i + nums[i])
return true
Interactive Visualization
Current Reachable Reached End Unreachable
Jump Array
Reach Bar
Step 0 of 0
Index
0
Max Reach
0
i + nums[i]
—
Result
—
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Jump Game
bool canJump(vector<int>& nums) { int maxReach = 0; for (int i = 0; i < nums.size(); i++) { if (i > maxReach) return false; maxReach = max(maxReach, i + nums[i]); } return true; }
Complexity
Time
O(N)
Single pass through the array.
Space
O(1)
Just one variable.