#55
Jump Game
Medium Furthest reach
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
nums[i] is the maximum jump length from index i. Starting at index 0, decide whether you can reach the last index.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you reach the last index?
Why this works: track the furthest index reachable. If you ever stand beyond it, you're stuck.
Example: [3, 2, 1, 0, 4]
reach 3, 3, 3, 3index 4 > reach 3 → false
✦Hints open one at a time
Track the furthest index you can reach so far.
If you ever stand on an index beyond that reach, you're stuck.
↗Approach
Scan i from 0; if i > reach return false; otherwise reach = max(reach, i + nums[i]). Return true when the scan finishes (or reach covers the end).
</>Solution (Java)
class Solution {
public boolean canJump(int[] nums) {
int reach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reach) return false; // can't even get here
reach = Math.max(reach, i + nums[i]);
}
return true;
}
}!Common mistake
Trying all jumps recursively — exponential without memoisation.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Greedy
🎬 Episodes 69–73: video coming soon