Cross The River On Stepping Stones
Stones sit at known positions across a river. A frog starts on the first stone. From a stone reached by a jump of k units, its next jump must be k-1, k, or k+1 units forward. Decide whether the frog can reach the last stone.
Problem
Given a sorted list of distinct stone positions stones (stones[0] = 0), determine if the frog can reach the last stone. The first jump must be exactly 1 unit. From a jump of size k landing on a stone, the next jump is k-1, k, or k+1 (must be positive). The frog can only land on stones.
Input
A sorted integer array stones with stones[0] = 0.
Output
A boolean — true if the last stone is reachable.
Constraints
- 2 ≤ n ≤ 2000
- 0 ≤ stones[i] ≤ 2^31 - 1
- stones is strictly increasing; stones[0] == 0.
Examples
Example 1
Input
[0,1,3,5,6,8,12,17]
Output
true
Jumps of 1,2,2,3,4,5 land exactly on the final stone.
Example 2
Input
[0,1,2,3,4,8,9,11]
Output
false
The gap to stone 8 is too large to bridge with the allowed jump sizes.