Fewest Leaps to the Far Bank
MediumGreedy
Problem
Same river as before: from stone i you may leap to any stone from i + 1 up to i + leaps[i]. This time the last stone is guaranteed to be reachable from stone 0.
Return the minimum number of leaps needed to get from stone 0 to the last stone.
Example 1
- Input:
- leaps = [2, 3, 1, 1, 4]
- Output:
- 2
0 → 1 (one leap), then 1 → 4 (second leap).
Example 2
- Input:
- leaps = [1, 2, 1, 1, 1]
- Output:
- 3
0 → 1 → 3 → 4, or 0 → 1 → 2 → 4.
Constraints
- 1 ≤ leaps.length ≤ 10^4
- 0 ≤ leaps[i] ≤ 1000
- The last stone is reachable.
Hint
Show the first hint
Group stones by the minimum number of leaps needed to reach them. What shape does each group have?
Walkthrough
How to approach it
01Clarify before coding
- Is reaching the last stone guaranteed? Yes, so no -1 case.
- If there is only one stone, how many leaps? Zero.
- Is overshooting the last stone allowed? Yes, it counts as reaching it.
02Brute force
DP: best[j] = 1 + min(best[i]) over every i < j with i + leaps[i] ≥ j.
Cost: O(n²) = 10^8 for n = 10^4: borderline and clearly not what is expected.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.