Jump Game
Problem statement
You are given a list of non-negative numbers nums. You start at index 0. The number at each index is the longest jump you can make from there: from index i you may move forward by any distance from 1 up to nums[i].
Return true if you can reach the last index, and false if you can't.
A value of 0 means you are stuck at that index unless you can jump past it from somewhere earlier.
Examples
Example 1
Input: nums = [2,3,1,1,4]
Output: true
Explanation: From index 0 jump 1 step to index 1, whose value is 3. From there a jump of 3 lands exactly on the last index.
Example 2
Input: nums = [3,2,1,0,4]
Output: false
Explanation: Every route from the start ends at index 3, whose value is 0. Nothing can jump past it, so index 4 is out of reach.
Hints
Approach
Optimal: Greedy farthest reach
Intuition
Here is the key observation: if you can reach some index, you can also reach every index before it (just jump shorter). So the set of reachable indexes is always one unbroken block starting at 0. That means a single number describes it completely — the farthest reachable index, farthest.
Walk left to right. At each index i that is inside the block (i <= farthest), you could stand there and jump up to i + nums[i], so stretch farthest to that if it's bigger. If you ever reach an index with i > farthest, there is a gap you can't cross, and the answer is false. If farthest reaches the last index, the answer is true. This is a greedy approach: at each step it keeps only the best reach so far and never reconsiders.
Steps
- Set
farthest = 0. - For each index
ifrom 0 ton - 1:- If
i > farthest, returnfalse(this index can't be reached). - Set
farthest = max(farthest, i + nums[i]). - If
farthest >= n - 1, returntrue.
- If
- Return
true(reached only when the list has one element, handled by the check above).
Dry run
nums = [3,2,1,0,4]
| i | nums[i] | i > farthest? | farthest after |
|---|---|---|---|
| 0 | 3 | no (0 ≤ 0) | 3 |
| 1 | 2 | no | max(3, 3) = 3 |
| 2 | 1 | no | max(3, 3) = 3 |
| 3 | 0 | no | max(3, 3) = 3 |
| 4 | 4 | yes (4 > 3) → return false |
For [2,3,1,1,4]: after index 0, farthest = 2; at index 1 it becomes 1 + 3 = 4, which is the last index → true. Edge case: [0] returns true at i = 0, because the start is already the last index.
Complexity
Time O(n) - We walk through the list once, doing a comparison and a `max` at each index. There is no inner loop, which is what makes this faster than the DP. We may even stop early, as soon as the last index is within reach. For 10,000 indexes that is at most 10,000 steps.
Space O(1) - Only one number is kept: the farthest index reachable so far. No list of flags, no recursion. The input is not counted.
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
last = len(nums) - 1
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
if farthest >= last:
return True
return True
if __name__ == "__main__":
print(str(Solution().canJump([2, 3, 1, 1, 4])).lower()) # true
print(str(Solution().canJump([3, 2, 1, 0, 4])).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: "can you reach the end?" where each position gives a maximum jump or reach
- Idea: walk left to right keeping
farthest = max(farthest, i + nums[i]); fail ifi > farthest - Cost: O(n) time, O(1) space
- Trap: trying every jump (exponential) or a DP (O(n²)) when one running maximum is enough
- Remember: reachable indexes form one unbroken block from 0 — that's why one number is enough
Interview follow-ups
Return the minimum number of jumps to reach the end.
This is Jump Game II. Keep the same left-to-right walk, but track the end of the current jump's range. When you pass that end, you must take another jump, so add one and set the new range end to the farthest reach seen so far. It is still O(n) time and O(1) space — a BFS in disguise, where each jump is one level.
Jumps can go backwards as well as forwards. What changes?
The reachable indexes are no longer one unbroken block, so the greedy stops working. Treat each index as a node with edges to the indexes it can reach, and run a BFS from index 0 with a
visitedlist. That costs O(n + total jumps), and you can stop as soon as the last index is reached.The list is too large to fit in memory and arrives as a stream. Can you still answer?
Yes, with the greedy. It only needs the current index and one number,
farthest, so read the values one at a time and never store the list. The moment the index passesfarthestyou can stop withfalse; if the stream ends while the index is still within reach, the answer istrue. Memory stays O(1) however long the stream is. The DP could not do this, because it walks from right to left and needs the whole list.
Frequently asked questions
Because reachable indexes always form one unbroken block from index 0. If you can reach index 5, you can reach 4, 3, 2 and 1 too, since every jump can be shorter than its maximum. So knowing only the farthest reachable index tells you everything. The greedy walk stretches that block as far as possible and fails only when it meets a gap.
Yes, you can walk backwards. Keep a goal, starting at the last index. From right to left, whenever i + nums[i] >= goal, index i can reach the goal, so move the goal to i. At the end, the answer is goal == 0. It is the same O(n) time and O(1) space; some people find it easier to explain.
Adding a memo (a stored answer per index) to the brute force gives the same O(n²) time as the bottom-up DP. It can overflow the call stack on long inputs, though: with 10,000 indexes, the recursion can go 10,000 calls deep, far past Python's default limit of 1,000. The bottom-up version avoids recursion entirely.
A 0 means you can't move forward from that index. It only blocks you if no earlier index can jump over it. In [2,0,1], index 0 jumps straight over the 0 to index 2, so the answer is true. In [1,0,1], the only way forward lands on the 0, so it is false. The greedy handles both automatically.
It is the classic warm-up for greedy reasoning: keep one running best value instead of exploring every option. The same "how far can I still reach?" idea shows up in coverage checks, such as whether a chain of relays or a set of overlapping time windows covers everything from start to end without a gap. It also tests that you can spot when a DP answer can be simplified to a single pass.
