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
Input:
stones = [0,1,3,5,6,8,12,17]Output:
trueExplanation:
Jumps: 0->1 (k=1), 1->3 (k=2), 3->5 (k=2), 5->8 (k=3), 8->12 (k=4), 12->17 (k=5). Reaches stone 17.
Input:
stones = [0,1,2,3,4,8,9,11]Output:
falseExplanation:
At stone 4 with k=1, next jump can be 0,1,2. Gap to stone 8 is 4 units - unreachable. No valid path exists.
Input:
stones = [0,1,3,6,10,15,21]Output:
trueExplanation:
Jumps: 0->1 (k=1), 1->3 (k=2), 3->6 (k=3), 6->10 (k=4), 10->15 (k=5), 15->21 (k=6). Perfect triangular sequence.
Constraints
- •
2 ≤ stones.length ≤ 2000 - •
0 ≤ stones[i] ≤ 2³¹ - 1