Accelerating Stone Hops
Problem
Stones in a river sit at increasing positions stones (in units), with stones[0] = 0 where a frog starts. The frog's first hop must be exactly 1 unit.
If its last hop was h units, the next hop must be h - 1, h or h + 1 units (always forward, so at least 1). The frog may only land on stones. Return true if it can reach the last stone.
Example 1
- Input:
- stones = [0, 1, 3, 5, 6, 8, 12, 17]
- Output:
- true
Hops 1, 2, 2, 3, 4, 5: 0 → 1 → 3 → 5 → 8 → 12 → 17.
Example 2
- Input:
- stones = [0, 1, 2, 3, 4, 8, 9, 11]
- Output:
- false
The gap from 4 to 8 needs a hop of 4, but the frog can be at most at speed 2 by stone 4.
Constraints
- 1 ≤ stones.length ≤ 2000
- 0 = stones[0] < stones[1] < ... ≤ 2^31 - 1
Hint
Show the first hint
The position alone is not enough to decide the future: the last hop length matters too.
Walkthrough
How to approach it
01Clarify before coding
- Is the first hop forced to 1? Yes, so if stones[1] != 1 the frog cannot move.
- Can hops go backwards or be 0? No, hops are at least 1.
- Are positions huge? Up to 2^31 - 1, so index stones through a hash map, not an array over positions.
02Brute force
DFS over (stone, last hop) trying the three next hops, without remembering visited states.
Cost: Up to 3^n branches: exponential.
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.