The problem
Same lily pads, and the last pad is always reachable. Find the fewest jumps needed to get there.
Input: [2, 3, 1, 1, 4] Output: 2 (pad 0 → pad 1 → last pad)
Picture it
Think in waves. Wave 0 is pad 0. Wave 1 is every pad reachable with one jump. Wave 2 is every pad reachable from wave 1, and so on. As we scan a wave we note how far its pads could jump; that becomes the end of the next wave. The number of waves needed to cover the last pad is the answer.
How to recognise it
- It is Jump Game again, but now you want the fewest jumps, and the last pad is guaranteed reachable.
- Reachable positions after k jumps form a range (everything up to some farthest point), so the jumps behave like the levels of a breadth-first search (BFS: explore everything one step away, then two steps away, and so on).
- Up to 10^4 pads. A quadratic table (about 5 × 10^7 steps) would be borderline; one pass is expected.
- When the answer is "number of levels until the target" and each level is a contiguous range, you can count levels by tracking the end of the current level and the farthest reach of the next.
Start with brute force
Try every jump length from every pad, recursively, and keep the smallest number of jumps.
def jump_brute(pads):
n = len(pads)
def go(i):
if i >= n - 1: return 0
best = float("inf")
for s in range(1, pads[i] + 1):
best = min(best, 1 + go(i + s))
return best
r = go(0)
return None if r == float("inf") else r
Each pad branches over all its jump lengths and nothing is remembered, so time is exponential, and the calls double with every extra pad (a row like [10, 9, …, 1, 1] of 11 pads makes 1,024 calls; 40 such pads would make about 5 × 10^11). A table d[j] = min(d[i] + 1) over earlier pads i that can reach j fixes the repetition but is O(n²). Space is O(n) for the recursion.
From brute force to the idea
- Think in waves. After 0 jumps you are at pad 0. After 1 jump you can be on any pad from 1 to
0 + pads[0]. After 2 jumps, on any pad up to the farthest reach of those pads. Each wave is a range. - Track the wave.
endis the last pad of the current wave, andfaris the farthest pad any pad in the current wave (so far) can reach. - Scan left to right. At pad i update
far = max(far, i + pads[i]). - Cut at the wave end. When
i == end, you have seen every pad of this wave, so one more jump is needed to leave it:hops += 1and the next wave ends atfar. - Stop before the last pad. The loop runs to
len(pads) - 2, because once you are standing on the last pad you are done.
This is the key idea: count the waves, where each wave ends at the farthest point the previous wave could reach.
The key idea
BFS by ranges: when i reaches the end of the current wave, jumps += 1 and the wave end becomes the farthest reach. O(n).
Python solution
def jump(pads):
hops, end, far = 0, 0, 0
for i in range(len(pads) - 1):
far = max(far, i + pads[i]) # best reach from this wave
if i == end: # finished the current wave
hops += 1
end = far
return hopsIn 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 jump lengths | O(n): recursion depth |
| Greedy waves (shown code) | O(n): each pad is looked at once | O(1): three variables |
Edge cases
- One pad (
[0]): returns0, since the loop range is empty. - Two pads (
[1, 2]): returns1. - Big first jump (
[5, 1, 1, 1, 1, 1]): returns1. - Example
[2, 3, 1, 1, 4]: returns2(jump to the 3, then to the end). - Zeros in the middle (
[2, 3, 0, 1, 4]): returns2. - Unreachable input (
[1, 0, 2]): the problem excludes it, but the code returns2instead of reporting failure, because it never checks reachability. - All ones (
[1, 1, 1, 1]): returns3.
Common mistakes
- Forgetting
return hopsafter the loop, so the function returnsNone. - Looping over the last pad too, which counts one extra jump whenever the last pad ends a wave (
[2, 3, 1, 1, 4]would give 3). - Updating
endbefore readingfarfor the current pad, which loses the reach of the pad that ends the wave. - Taking the jump that goes farthest from the current pad. The right choice is the pad in the wave whose reach goes farthest, which the
farvariable captures.
The last pad is no longer guaranteed to be reachable. Return the fewest jumps, or -1 if it cannot be reached. For [3, 2, 1, 0, 4] the answer is -1. Describe your approach, then write it if you like.
Compare with our answer
The same waves apply, with one extra test: if far has not moved past the current pad, there is no way forward.
def jump_or_minus1(pads):
hops, end, far = 0, 0, 0
for i in range(len(pads) - 1):
far = max(far, i + pads[i])
if far <= i: # stuck: nothing reaches past pad i
return -1
if i == end:
hops += 1
end = far
return hops
jump_or_minus1([2, 3, 1, 1, 4]) is 2, jump_or_minus1([3, 2, 1, 0, 4]) is -1 and jump_or_minus1([0]) is 0. Time O(n), space O(1).
A strong answer mentions: the wave end and farthest reach, failing when far does not extend past the current pad, returning hops at the end, and handling the one-pad case.
1. A frog crosses n lily pads, and from pad i it can jump any distance up to lim[i]. The far bank is always reachable. You want the fewest jumps for n up to 10,000. Which approach fits best?
Each jump leads to a range of pads, so counting wave ends gives the answer in O(n). Jumping the maximum from the current pad can skip a pad whose own jump goes farther, and the recursive search is exponential.
2. A learner deletes the last line, return hops. What does [2, 3, 1, 1, 4] give?
Without a return statement Python gives back None after the loop, even though hops reached 2 inside it. The values 3 and 0 would need other mistakes.
3. A learner changes the loop to for i in range(len(pads)): and keeps return hops. What does [2, 3, 1, 1, 4] give?
The extra last iteration meets i == end on the final pad and adds a third jump. The loop must stop before the last pad, since being on it already finishes the journey.
Score 60% or more and the lesson is marked complete.