Frog Jump
Hard · Dynamic Programming · Array · Dynamic Programming · Hash Table
Problem
A frog crosses a river by hopping on stones. stones lists the stone positions in strictly increasing order. The frog starts on the first stone, at position 0, and its first hop must be exactly 1 unit.
If its previous hop was k units, its next hop must be k - 1, k or k + 1 units, always forward, and it must land on a stone.
Return true if the frog can reach the last stone, otherwise false.
Examples
Input: stones = [0,1,3,5,6,8,12,17] Output: true
Hop 1, 2, 2, 3, 4, 5: 0 → 1 → 3 → 5 → 8 → 12 → 17.
Input: stones = [0,1,2,3,4,8,9,11] Output: false
The longest hop that can reach 4 is 2, so the next hop is at most 3 and 8 is out of reach.
Input: stones = [0,2] Output: false
The first hop must be 1, and there is no stone at position 1.
Constraints
- 2 <= len(stones) <= 2000
- 0 <= stones[i] <= 2^31 - 1
- stones[0] == 0
- stones is strictly increasing
Approaches
- Baseline: depth-first search over hops — time O(3^n), space O(n)
Follow-up
A hop of length k onto stone i needs at least k earlier stones, so k < i and there are O(n²) states. The DFS baseline with a memo on (stone, k) has the same bound. The use cases ask for the fewest hops and for the farthest stone the frog can reach.
Related problems
Start free on Cariara · Coding problems · System design studio
