332. Frog Jump
A frog is crossing a river on stones. You are given a strictly increasing array stones, the positions of the stones in the water; the frog starts on the first stone, which is always at position 0.
The very first hop must cover exactly 1 unit. From then on, if the previous hop covered k units, the next hop must cover k - 1, k, or k + 1 units — always forward — and it must land exactly on a stone. Return true if the frog can reach the last stone this way, and false otherwise.
Notice that the frog's situation is not just "which stone am I on": two arrivals at the same stone with different last-hop sizes open different futures. That pair — (stone, last hop size) — is the state your solution should reason about.
Example 1:
Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]
Output: true
Explanation: One winning route: hop 1 unit to position 1, then 2 to 3, 2 to 5, 3 to 8, 4 to 12, and finally 5 to 17. Every hop grows by at most one unit and always lands on a stone.
Example 2:
Input: stones = [0, 1, 2, 3, 4, 8, 9, 11]
Output: false
Explanation: Crossing from position 4 to 8 needs a 4-unit hop, but hopping along the tightly packed stones 0..4 can only build the hop size up to 2 by then — the gap is unbridgeable, so the far bank is unreachable.
Constraints:
- 2 ≤ stones.length ≤ 2000
- 0 ≤ stones[i] ≤ 2³¹ - 1
- stones is strictly increasing and stones[0] = 0.
Hints:
If the second stone is not at position 1, the frog is stuck immediately — the first hop is forced. More generally, the frog's state is the pair (stone index, last hop size), not the stone alone.
The hop size when standing on the i-th stone can never exceed i + 1 (it grows by at most 1 per hop), so there are only O(n²) distinct states. Memoize a DFS over (index, lastHop), or fill in forward: for each stone keep the set of hop sizes that can land there, and from each push k-1, k, k+1 to the stones they reach.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]
Expected output: true