Jump Game
You stand on index 0 of the array nums. From index i you may jump forward by any number of steps from 1 up to nums[i], so nums[i] is your longest jump from there and a 0 means you cannot move. Return true if some sequence of jumps lands on the last index, and false otherwise.
Function
- numsinteger-array
- the longest jump you can make from each index
- Returnsboolean
- true if you can land on the last index starting from index 0, otherwise false
Constraints
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 105- A jump may be shorter than
nums[i], so a long jump never forces you past the last index.
Examples
- Input
- nums = [2, 0, 3, 1, 0, 2]
- Output
- true
- Explanation
- From index 0 you can reach index 1 or 2. Index 1 holds 0 and is a dead end, but index 2 holds 3 and reaches index 5, the last index.
- Input
- nums = [1, 3, 0, 0, 0, 2]
- Output
- false
- Explanation
- Index 0 can only step to index 1, and index 1 reaches at most index 4. Indices 2, 3 and 4 all hold 0, so nothing ever gets past index 4 to index 5.
- Input
- nums = [0]
- Output
- true
- Explanation
- The array has one element, so you start on the last index and need no jump at all.
+18 hidden tests on Submit
Follow-up
Count the different jump sequences that land on the last index, modulo 10^9+7, still in O(n) time.
Hints
Open them one at a time. Each one gives away a little more.
A
0traps you only when nothing before it can jump past it. What would you need to know about the indices before it to tell?If you can reach index
i, you can reach every index fromiup toi+nums[i], because shorter jumps are allowed. So the reachable indices always form one unbroken block that starts at index 0.Walk from left to right and keep
farthest, the right end of that block. If the current index is beyondfarthest, it can never be reached. Otherwise stretchfarthesttoi+nums[i]when that is larger. If the walk gets through the whole array, the last index is reachable.
Solution
The number of possible routes grows exponentially, so checking routes one by one cannot work on long arrays. The key fact is that the indices you can reach always form one unbroken block starting at index 0. One number, the right end of that block, holds everything you need, and a single pass decides the answer.
Try every jump
Correct, but does not finish on the largest tests
Intuition
The most direct idea is to act it out. Stand on index 0 and try every landing spot your jump allows, one by one. From each landing spot, do the same again. If any branch lands on the last index, the answer is true. If every branch runs into a dead end, it is false.
On the first example, index 0 holds 2, so you try index 1 and index 2. Index 1 holds 0, a dead end, so you back up and try index 2. Index 2 holds 3 and reaches index 5, the last index, and the search stops with true.
The search is correct because it looks at every route. That is also its problem: it never remembers an index it already explored, so it explores the same index again for every route that reaches it. When the answer is false, it has to rule out every route. In [4, 3, 2, 1, 0, 5] every index before the 0 can reach the 0, which gives 8 different routes into it. With 30 such indices there are more than 500 million routes, and the largest tests have 10,000 elements. A route that long also overflows the call stack in some languages: Python stops at 1,000 nested calls by default.
Algorithm
- Write a helper
reach(i)that answers: can you get from indexito the last index? - If
iis the last index, returntrue. - Otherwise try every landing spot
nextfromi+1tomin(i+nums[i], n-1), and returntrueas soon asreach(next)does. - If no landing spot works, return
false. - The answer is
reach(0).
def canJump(nums):
last = len(nums) - 1
def reach(i):
# Can you get from index i to the last index?
if i == last:
return True
for nxt in range(i + 1, min(i + nums[i], last) + 1):
if reach(nxt):
return True
return False
return reach(0)Remember which indices can finish
Correct, but does not finish on the largest tests
Intuition
The search above asks the same question, "can index j finish?", over and over. The answer for j never changes, so work it out once and store it. Call an index good when you can get from it to the last index. The last index is good. Any other index i is good when at least one index it can land on, from i+1 to i+nums[i], is good.
Each index depends only on indices to its right, so fill a table good from right to left. In the first example, index 5 is good. Index 4 holds 0, so it is not. Index 3 reaches only index 4: not good. Index 2 reaches indices 3, 4 and 5, and 5 is good, so 2 is good. Index 1 holds 0: not good. Index 0 reaches 1 and 2, and 2 is good, so the answer is true.
Each index is now decided once, but deciding it can still scan up to n cells. In [9998, 9997, …, 1, 0, 7] every index can reach the 0 and nothing beyond it, so each one scans its whole range and finds nothing good. That is about 5 × 10^7 checks for 10,000 elements, and the largest tests are built like this one. The work grows with the square of the length, so it runs out of time on them.
Algorithm
- Make a boolean array
goodof lengthnand setgood[n-1]to true. - Go through
ifromn-2down to 0. - Scan
jfromi+1tomin(i+nums[i], n-1). If anygood[j]is true, setgood[i]to true and stop scanning. - Return
good[0].
def canJump(nums):
n = len(nums)
good = [False] * n # good[i]: from i you can reach the last index
good[n - 1] = True
for i in range(n - 2, -1, -1):
for j in range(i + 1, min(i + nums[i], n - 1) + 1):
if good[j]:
good[i] = True
break
return good[0]Track the farthest reachable index
Intuition
Look at which indices you can reach, not at the routes. From index i you may land on any index from i+1 to i+nums[i], with no gaps. So once index i is reachable, every index up to i+nums[i] is reachable too. Start with only index 0 and keep adding these stretches. Each new stretch starts inside the block you already have, so the reachable indices always form one unbroken block, [0, farthest].
That is why one number is enough. Walk i from left to right. While i ≤ farthest, index i is reachable, so stretch farthest to max(farthest, i+nums[i]). If i ever passes farthest, no reachable index jumps to i. The block cannot grow across that gap, so nothing to the right of it is reachable, the last index included. If the walk gets to the end with no gap, the last index is reachable.
In the second example, farthest is 0, then 1 after index 0, then 4 after index 1. Indices 2, 3 and 4 hold 0 and leave it at 4. Index 5 is past 4, so the answer is false. In the first example, index 2 pushes farthest to 5 and no index is ever past it, so the answer is true.
Why is keeping only the largest reach safe? You never commit to a jump. The block holds every index that any route can reach, and every shorter landing spot lies inside it. Throwing away everything but the right end loses no information.
Algorithm
- Set
farthest = 0. - For each index
ifrom left to right: ifi > farthest, returnfalse. - Otherwise set
farthest = max(farthest, i+nums[i]). - If the loop finishes, every index was reachable, so return
true.
def canJump(nums):
farthest = 0 # every index up to farthest can be reached
for i, jump in enumerate(nums):
if i > farthest:
return False # nothing reachable jumps to i
farthest = max(farthest, i + jump)
return True
Pitfalls and edge cases
Most wrong answers come from reading nums[i] as the only jump, or from the order of the two checks inside the loop.
- Always jumping exactly
nums[i]steps, or always taking the longest jump. With[2, 5, 0, 0]the full jump from index 0 lands on a 0, while the 1 step jump to index 1 reaches the end. - Returning
falseas soon as you see a 0. A 0 matters only when nothing before it jumps past it:[2, 0, 1]jumps over the 0 and the answer istrue. - Updating
farthestbefore checkingi > farthest. An index you cannot reach must not stretch the block, so check first, then update. - Treating a one element array as a failure. You already stand on the last index, so the answer is
true, even when that element is 0. - Recursing on long arrays. A route can be 10,000 jumps long, which overflows the call stack in several languages. The single pass uses no recursion.
Frequently asked questions4
What is the time complexity of Jump Game?
The farthest reach pass visits each index once, so it runs in O(n) time with O(1) extra space. The table approach is O(n²) in the worst case, and trying every route is exponential.
Why does the greedy approach work for Jump Game?
Because shorter jumps are allowed, reaching index i means you can reach every index up to i+nums[i]. Those stretches always overlap the part already reached, so the reachable indices form one block starting at 0. The greedy pass tracks only that block's right end, which describes the whole block, so it never discards a route that could have worked.
Is Jump Game a dynamic programming problem?
It can be solved with dynamic programming: mark each index good when one of its landing spots is good, filling the table from right to left. That costs O(n²). Notice that only the leftmost good index matters, since any index that reaches a good index reaches the leftmost one too. Keep only that index, goal, and move it to i whenever i+nums[i] ≥ goal. The answer is whether goal ends at 0, an O(n) pass that mirrors the greedy one.
How do you find the minimum number of jumps?
Use the same farthest reach idea in layers. Keep the end of the block you can reach with the current number of jumps and the farthest index the next jump can reach. When i passes the end of the current block, you need one more jump, and the next block ends at that farthest index. It is still one O(n) pass.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def canJump(nums):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [2, 0, 3, 1, 0, 2]
Expected
true