Description
A frog crosses a river by jumping on stones. Given stone positions, determine if the frog can reach the last stone. It can jump k-1, k, or k+1 units if its last jump was k units.
Examples
stones = [0,1,3,5,6,8,12,17]trueFrog can reach the last stone.
stones = [0,1,2,3,4,8,9,11]falseThe frog can reach stone 4 with a jump of 1, but the gap to stone 8 is 4 units, which exceeds the maximum next jump of 2 (previous jump 1, plus 1). There is no valid sequence of jumps to reach the last stone.
stones = [0,1,3,6,10,15,21]trueThe frog starts at stone 0 and makes its first jump of 1 unit to stone 1. From stone 1, it can jump 1 or 2 units - it chooses 2 units to reach stone 3. From stone 3, it jumps 3 units to stone 6. From stone 6, it jumps 4 units to stone 10. From stone 10, it jumps 5 units to stone 15. Finally, from stone 15, it jumps 6 units to reach the last stone at position 21. The jump sequence is [1,2,3,4,5,6], where each jump differs by at most 1 from the previous jump.
Constraints
- •
2 ≤ stones.length ≤ 2000 - •
0 ≤ stones[i] ≤ 2³¹ - 1