574. Fewest Jumps
A courier crosses a river on stepping platforms numbered 0 to n - 1, starting on platform 0. From platform i the courier may leap forward any distance from 1 to jumps[i] platforms (a value of 0 means no leap is possible from there).
Return the minimum number of leaps needed to land on platform n - 1. If n == 1 the courier is already there and the answer is 0.
The input is always valid: the last platform can be reached from the start. Your solution should run in O(n) time with O(1) extra space; an O(n^2) table of best leap counts is too slow for the largest rivers.
Example 1
- Input:
- jumps = [4,1,1,3,1,1,1]
- Output:
- 2
- Explanation:
Leap from platform 0 to platform 3, then leap 3 platforms onto the last one: 2 leaps.
Example 2
- Input:
- jumps = [1,1,1,1]
- Output:
- 3
- Explanation:
Every platform allows only a one-step leap, so three leaps are required.
Example 3
- Input:
- jumps = [2,5,1,1,1,1,1]
- Output:
- 2
- Explanation:
Leap to platform 1, which can reach platform 6 directly, giving 2 leaps.
Constraints
1 ≤ jumps.length ≤ 1000000 ≤ jumps[i] ≤ 100000- The last platform is always reachable from platform
0.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)