The problem
Each number says the longest jump you may make from that position. Starting at the first position, can you reach the last one?
Input: [2, 3, 1, 1, 4] Output: true
Picture it
Picture a frog on a row of lily pads. Each pad shows its jump range. Walking along the pads, we keep track of the farthest pad reachable so far. If we ever stand on a pad beyond that point, we could never have got here, so the frog is stuck. If the farthest reach covers the last pad, the answer is yes.
How to recognise it
- Each position gives a maximum jump, and any shorter jump is also allowed, so reachability has no gaps: if you can get to position p, you can get to every position before p that you passed.
- The question is yes or no ("can I reach the end?"), not "how", so you only need to track a single frontier.
- Up to 10^4 positions with jumps up to 10^5, so exploring every path is hopeless.
- When "the set of reachable positions" is always a prefix, keep one number: the farthest position reachable so far.
Start with brute force
Try every jump length from each position, depth first, and report whether any path reaches the last position.
def can_jump_brute(pads):
last = len(pads) - 1
def go(i):
if i >= last:
return True
for step in range(1, pads[i] + 1):
if go(i + step):
return True
return False
return go(0)
Without remembering failures, the same positions are explored again and again. For a row like [k-1, k-2, …, 1, 0, x] where the end is unreachable, the number of calls doubles with every extra pad: 25 pads already means about 8 million calls, and the limit is 10,000. Space is O(n) for the recursion.
From brute force to the idea
- Find the waste. The brute force explores each pad from every path that reaches it, but a pad is either reachable or not.
- Reachable positions form a prefix. If you can reach position p, you can land on any earlier position by choosing a shorter jump. So everything from 0 to the farthest reachable position is reachable.
- Track one number. Let
reachbe the farthest index reachable so far. Scan left to right; at pad i, the jump from i can extend it:reach = max(reach, i + jump). - Detect failure. If the scan arrives at a pad i with
i > reach, nothing could reach it, and nothing beyond, so returnFalse. - Success. If the loop finishes, every pad including the last was within reach, so return
True.
This is the key idea: reachability is a prefix, so keep the farthest reach and check each pad against it.
The key idea
Greedy: reach = max(reach, i + nums[i]); fail if i > reach. O(n).
Python solution
def can_jump(pads):
reach = 0
for i, jump in enumerate(pads):
if i > reach:
return False # this pad can never be reached
reach = max(reach, i + jump)
return TrueIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: every pad branches over all its jump lengths | O(n): recursion depth |
| Greedy reach (shown code) | O(n): one pass, one comparison and one max per pad | O(1): a single variable |
Edge cases
- One pad (
[0]): returnsTrue; you are already at the end. - Stuck on a zero (
[3, 2, 1, 0, 4]): returnsFalse; the farthest reach is 3, and the zero is a wall. - Zero that can be jumped over (
[2, 3, 1, 1, 4]): returnsTrue. - Start is zero but there is more (
[0, 1]): returnsFalse. - Zero in the middle but reachable (
[2, 0, 0]): returnsTrue; the first pad jumps straight to the end. - Empty list: returns
Truebecause the loop never runs; the problem guarantees at least one pad. - Huge jump (
[100000, 0, 0]): returnsTrue; reach goes past the end, which is fine.
Common mistakes
- Overwriting instead of taking a maximum (
reach = i + jump), so a later short jump shrinks the reach:[3, 0, 0, 0]wrongly returnsFalse. - Checking
i >= reachinstead ofi > reach, which rejects even the starting pad. - Returning
Falseas soon as a pad holds 0. A zero is a wall only whenreachcannot get past it, as[2, 0, 0]shows. - Building a full table of reachable positions. It works in O(n²) but wastes the prefix property.
Return the number of positions you can reach from the first pad (counting the first). For [3, 2, 1, 0, 4] the answer is 4 (positions 0 to 3), and for [2, 3, 1, 1, 4] it is 5. Describe your approach, then write it if you like.
Compare with our answer
The same scan works. When the scan arrives at a pad it cannot reach, the pads before it are exactly the reachable ones.
def count_reachable(pads):
reach = 0
for i, jump in enumerate(pads):
if i > reach:
return i
reach = max(reach, i + jump)
return len(pads)
count_reachable([3, 2, 1, 0, 4]) is 4 and count_reachable([0, 1]) is 1. Time O(n), space O(1).
A strong answer mentions: that reachable positions form a prefix, returning the index of the first unreachable pad, returning the full length if the scan finishes, and the same single-variable reach.
1. Stepping stones are laid in a row, and from stone i you may jump any distance up to limit[i]. With 10,000 stones, how do you decide if the last stone can be reached from the first?
Reachable stones form a prefix, so the farthest reach is all you need, in O(n) time. Always jumping the maximum can skip over the last stone, and sorting loses the positions. Plain depth-first search is exponential in bad cases.
2. Why is the shown code O(n) time even though each pad allows many jump lengths?
Taking max(reach, i + jump) covers all shorter jumps at once, since any shorter jump lands inside the same prefix. The code does not stop at zeros (it only fails when a pad is beyond the reach) and uses no dictionary.
3. A learner changes the update to reach = i + jump (no max). For which input does the function now return the wrong answer?
After pad 0 the reach is 3, but pad 1 overwrites it with 1, so pad 2 is judged unreachable and the function returns False instead of True. The other inputs give the right answers (True, False, True) even with the overwrite.
Score 60% or more and the lesson is marked complete.