Jump Game
Jump Game is LeetCode 55 (Medium). You start at index 0 of an integer array nums. The value nums[i] is the longest jump you may take from index i; any shorter jump is allowed too. Return true if you can reach the last index, otherwise false.
numsholds 1 to 10⁴ values, each between 0 and 10⁵.- A 0 means you cannot move forward from that index.
Trying every sequence of jumps grows exponentially, and marking reachable cells one by one is O(n²). One pass is enough.
- 1 <= nums.length <= 10⁴
- 0 <= nums[i] <= 10⁵
Intuition
You never need to know which jumps to take, only the furthest index you can reach so far. Call it maxReach.
If you can stand on some index, you can stand on every index before it too, because any jump can be cut short. So the reachable indices always form one unbroken block, from 0 up to maxReach.
Walk left to right. Every index inside the block may push maxReach further, to i + nums[i]. The only way to fail is to arrive at an index beyond maxReach: no jump lands there, so nothing after it is reachable either. That is the whole jump game greedy: one pass, one number.
"Can you get from the start to the end" on an array of ranges is a reach problem: keep the furthest point covered so far instead of following paths. The jump game LeetCode series continues with Jump Game II (45), which counts the jumps, and Video Stitching (1024) uses the same idea on clips.
Approach
Before reading on, run [3,2,1,0,4] by hand and write down the furthest reachable index after each step. At which index does it become clear the answer is false?
Two ways to solve it
Scan left to right and keep maxReach, the furthest index any reachable spot can jump to.
- Fails fast: stops at the first index it cannot reach.
- Ends early: breaks once the end is covered.
- State: one integer.
The version most interviewers expect.
Scan right to left with goal, the leftmost index known to reach the end. An index that can jump to goal becomes the new goal.
- Answer:
truewhengoalends at 0. - No early exit: always visits every index.
- State: one integer.
Same cost, and some find it easier to prove.
Both make one pass with one integer; the forward scan can also stop early, at the first gap or once the end is covered. The steps, code and live demo below follow the forward scan; the backward code comes after the demo.
Start with a reach of 0
Set maxReach = 0. Before any jump you stand on index 0, so it is the only index known to be reachable. Nothing further counts as reachable until some index's jump covers it.
Check the index before using it
For each index i, first test i > maxReach. If it is true, no jump from a reachable index lands on i, and every later index is even further away, so return false straight away.
Extend the reach
Otherwise i is reachable, so every index up to i + nums[i] is reachable as well. Set maxReach = max(maxReach, i + nums[i]). Taking the maximum keeps the best reach found so far; a short jump from here cannot shrink it.
Stop once the end is covered
As soon as maxReach >= n - 1, some chain of jumps lands on the last index, so break and return true. If the loop ends without finding a gap, the answer is true as well. In the jump game Python code, enumerate gives both i and nums[i].
Jump Game solution in Python | C++ | Java
maxReach will grow as the scan finds longer jumps; the last index is 4.maxReach becomes 2.maxReach becomes 4.maxReach = 4 is at least the last index 4, so some chain of jumps lands on it. Indices 2 to 4 are never visited.maxReach, so the last index can be reached. The exact jumps were never needed, only the furthest reach.maxReach will grow as the scan finds longer jumps; the last index is 4.maxReach becomes 3.maxReach stays the same.maxReach stays the same.maxReach is still 3.maxReach = 3, so no jump from any reachable index lands on it. Every later index is even further away, so the last index cannot be reached: return false.maxReach will grow as the scan finds longer jumps; the last index is 4.maxReach becomes 2.maxReach is still 2.maxReach becomes 4.maxReach = 4 is at least the last index 4, so some chain of jumps lands on it. Indices 3 to 4 are never visited.maxReach, so the last index can be reached. The exact jumps were never needed, only the furthest reach.maxReach will grow as the scan finds longer jumps; the last index is 0.maxReach = 0 is at least the last index 0, and you are already standing on it. maxReach, so the last index can be reached. The exact jumps were never needed, only the furthest reach.Backward greedy (moving goal)
goal starts at the last index. Walking from right to left, any index whose jump reaches goal can itself reach the end, so it becomes the new goal; the start works if the goal moves all the way to 0.
Common pitfalls
Extending the reach before checking the index
maxReach = max(maxReach, i + step)
if i > maxReach:
return Falseif i > maxReach:
return False
maxReach = max(maxReach, i + step)Extending first uses the jump of an index you may never stand on. On [0, 2, 0] index 1 is unreachable, but its jump of 2 is counted and the answer comes out true instead of false.
Always taking the longest jump
i = 0
while i < len(nums) - 1:
if nums[i] == 0:
return False
i += nums[i]
return Truefor i, step in enumerate(nums):
if i > maxReach:
return False
maxReach = max(maxReach, i + step)The longest jump can land on a 0 while a shorter one leads on. On [2, 3, 0, 0, 4] it jumps to index 2 and gets stuck, but 0 → 1 → 4 works. Tracking the reach considers every landing spot at once.
Edge cases
[0]You already stand on the last index. maxReach = 0 = n − 1, so the answer is true with no jump at all.
[2, 0, 2, 0, 1]Index 0 already reaches index 2, so the 0 at index 1 never blocks. A 0 only stops you when maxReach ends exactly on it.
Complexity
nums with a single integer, and it often stops early.Jump Game vs Jump Game II
The two problems share an input and are often confused. They ask different questions, so the greedy keeps different state.
| Jump Game (55) | Jump Game II (45) | |
|---|---|---|
| Question | can you reach the last index? | fewest jumps to reach it |
| Reachable? | not always | guaranteed |
| Greedy keeps | furthest reach | furthest reach and the end of the current jump |
| Returns | true / false | a count |
Jump Game FAQ
Is Jump Game greedy or dynamic programming?
Both work. A DP table marks each index reachable or not, which costs O(n²) in the worst case because each index can mark up to nums[i] others. The greedy keeps only the furthest reach, which is all the table ever needed, so it runs in O(n).