DSA problem
Frog Jump
A frog is at the first stone in a river. The positions of stones are given in a strictly increasing array stones. The frog can jump only forward and lands exclusively on stones. The first jump must be of length 1. After a jump of length k, the next jump must be of length k - 1, k, or k + 1 and must always be at least 1. Determine whether the frog can reach the last stone.
The natural state is the pair (stone_position, last_jump_size): from this state the frog can jump to stone_position + k - 1, stone_position + k, or stone_position + k + 1 as long as the destination is also a stone and k - 1 >= 1. A direct DFS/BFS over these states risks revisiting the same (position, k) repeatedly, so memoization is essential.
The cleanest formulation uses a hash map reach from each stone position to the set of jump sizes by which the frog can arrive at that stone. Initialize reach[stones[0]] = {0} (we arrived with zero last-jump from the start, allowing a first jump of size 1). For each stone in order, for each k in reach[s], try jump sizes k - 1, k, k + 1 (skipping non-positive ones). Each destination s + k' that is in the stone set gets k' added to its reach set.
If at any point the last stone's reach set becomes non-empty, return true. Otherwise, after processing all stones, return false. The number of distinct (position, k) states is bounded by n^2 since the jump size after t jumps is at most t + 1 and t < n. Total: O(n^2) time and space.
Examples
stones = [0,1,3,5,6,8,12,17]truestones = [0,1,2,3,4,8,9,11]falsestones = [0,1]trueConstraints
- 2 <= stones.length <= 2000
- 0 <= stones[i] <= 2^31 - 1
- stones[0] == 0
- stones is sorted in strictly increasing order.
- The first jump must be of length 1; after a jump of size k the next is k - 1, k, or k + 1 (always >= 1).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.