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.
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
Trying routes one by one takes exponential time. Look at the indices instead: the ones you can reach always form one unbroken block starting at index 0. The right end of that block holds everything you need, and one pass decides the answer.
Try every jump
Correct, but does not finish on the largest tests
Intuition
From index 0, try every landing spot in turn, and from each one do the same again. If any branch lands on the last index, the answer is true. The search is correct because it tries every route.
It never remembers an index it already explored, so 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 routes into it. With 30 such indices there are more than 500 million.
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
Call an index good when you can finish from it. The last index is good, and index i is good when some index from i+1 to i+nums[i] is good. Each index depends only on indices to its right, so fill a table from right to left and decide each index once. In the first example, index 2 reaches index 5, so it is good, and so is index 0, which reaches index 2.
Deciding one index can still scan n cells. In [9998, 9997, …, 1, 0, 7] every index reaches the 0 and nothing past it, so each scans its whole range: about 5 × 10^7 checks for 10^4 elements.
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
From a reachable index i you may land anywhere from i+1 to i+nums[i], with no gaps. That stretch starts inside the block already reached, so the block grows without holes and is always [0, farthest].
Walk i from left to right. While i ≤ farthest, index i is reachable and stretches farthest to max(farthest, i+nums[i]). If i passes farthest, no reachable index jumps to i, and the block can never cross that gap, so the last index is out of reach. Keeping only the right end loses nothing: you never commit to a jump, and every shorter landing spot lies inside the block.
In the second example, farthest goes 0, 1, 4 and stays at 4 across the three zeros. Index 5 is past it, so the answer is false.
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
- Always jumping exactly
nums[i]steps. 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.[2, 0, 1]jumps over the 0 and the answer istrue. - Updating
farthestbefore checkingi > farthest. An unreachable index must not stretch the block. - Treating a one element array as a failure. You already stand on the last index, even when it holds 0.
- Recursing on long arrays. A route can be 10,000 jumps long, which overflows the call stack in several languages; Python stops at 1,000 nested calls by default.
Frequently asked questions3
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.
Is Jump Game a dynamic programming problem?
It can be: mark each index good when one of its landing spots is good, from right to left, in O(n²). Only the leftmost good index found so far matters, since an index that reaches any good index to its right reaches that one too. Move that goal to i whenever i+nums[i] ≥ goal.
How do you find the minimum number of jumps?
Use the farthest reach idea in layers. Track 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, count one more jump and extend the block to 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.
def canJump(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [2, 0, 3, 1, 0, 2]
Expected Output
true