Frog Jump - Solution & Explanation
Problem Statement
A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.
If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.
Example 1:
Input: stones = [0,1,3,5,6,8,12,17] Output: true Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
Input: stones = [0,1,2,3,4,8,9,11] Output: false Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
Constraints:
2 <= stones.length <= 20000 <= stones[i] <= 231 - 1stones[0] == 0stonesis sorted in a strictly increasing order.
Approach Overview
Problem Overview: You are given an increasing array of stone positions in a river. The frog starts on the first stone and must reach the last one. If the previous jump length was k, the next jump can only be k-1, k, or k+1. The task is to determine whether the frog can reach the final stone.
Approach 1: Dynamic Programming with Hash Map (Time: O(n^2), Space: O(n^2))
This approach tracks all valid jump lengths that can land on each stone. Use a hash map where the key is the stone position and the value is a set of jump sizes that can reach that stone. Start with the first stone having jump length 0. For every reachable jump size k, try the next jumps k-1, k, and k+1. If a resulting position exists in the map, record that jump size for the destination stone. The key insight is that multiple paths may reach the same stone with different jump lengths, so storing all possibilities avoids recomputation. Since each stone may track up to O(n) jump sizes, the total complexity becomes O(n^2). This technique combines state tracking and quick membership checks using a hash map, a common pattern in dynamic programming problems.
Approach 2: DFS with Memoization (Time: O(n^2), Space: O(n^2))
This approach treats the problem as a state search. A state is defined by (currentStone, lastJump). From each state, recursively attempt jumps of lastJump - 1, lastJump, and lastJump + 1. Use a hash set for constant-time lookup of valid stone positions. Memoization stores failed states so the algorithm never explores the same combination twice. Without memoization, the recursion tree grows exponentially. With caching, the number of states is bounded by the number of stones times possible jump sizes, resulting in O(n^2) complexity. This method feels natural if you think of the problem as exploring reachable paths in a graph, using recursion and caching typical in dynamic programming and array traversal problems.
Recommended for interviews: The dynamic programming hash map solution is usually the expected answer. It demonstrates strong state modeling and efficient lookups. Explaining the DFS state transition first helps show intuition, but converting it into memoized DP shows deeper problem-solving skill and avoids exponential recursion.
Approach 1: Dynamic Programming with Hash Map
This approach uses dynamic programming with a hash map to store the possible jump lengths from each stone. Starting with the first stone and a jump of length 1, iterate through the stones, updating possible resultant jumps from each stone using the previously calculated jump lengths. Hash maps assist in efficiently checking if a stone can be reached from any prior stone using three different jump lengths.
The solution starts by checking if the first jump to the second stone is valid. It initializes a map, stone_dict, to keep track of possible jump lengths for each stone. It iterates through each stone and for each available jump length, calculates possible steps (current, one less, and one more unit) and checks if they can land on a valid stone. If so, it records the step in the map. The function then checks if there are any valid jumps recorded for the last stone.
Code
Python
JavaScript
Complexity
Time Complexity: O(n^2), where n is the number of stones. This accounts for the iteration over the stones and the potential steps from each stone.
Space Complexity: O(n), used by the hash map to store possible jump lengths.
Approach 2: DFS with Memoization
Use a depth-first search (DFS) approach combined with memoization to explore possible paths from the starting stone. The memoization helps in reducing repeated calculations by storing results of previously computed states (stone, jump_length). This approach recursively tries all possible jumps from a stone and checks if the end can be reached.
The C++ solution utilizes DFS with memoization. The canCross method initializes the process, calling a recursive dfs function starting from the first stone. This function tries all jump possibilities and checks if the final stone can be reached. The memo map tracks the states already visited. If the end stone is reached, it returns true. One unique aspect is using lower_bound to efficiently determine if a jump can directly land on a next stone.
Complexity
Time Complexity: O(n^2), potentially exploring all jump states for each stone.
Space Complexity: O(n^2), maintaining memoization of states.
Approach 3: Hash Table + Memoization
We use a hash table pos to record the index of each stone. Next, we design a function dfs(i, k), which means that the frog jumps from the i-th stone and the last jump distance is k. If the frog can reach the end, the function returns true, otherwise it returns false.
The calculation process of function dfs(i, k) is as follows:
If i is the index of the last stone, the frog has reached the end, and return true;
Otherwise, we need to enumerate the frog's next jump distance j, where j \in [k-1, k, k+1]. If j is a positive integer and the hash table pos exists the position stones[i] + j, then the frog can choose to jump j units on the i-th stone, if dfs(pos[stones[i] + j], j) returns true, the frog can successfully jump to the end from the i-th stone, and we can return true.
The enumeration is over, indicating that the frog cannot choose the appropriate jump distance on the i-th stone to jump to the end, so we return false.
In order to prevent repeated calculations in the function dfs(i, k), we can use memoization, record the result of dfs(i, k) in an array f, and assign f[i][k] each time the function dfs(i, k) returns result, and return f[i][k] directly when encountering dfs(i, k) next time.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the number of stones.
Approach 4: Dynamic Programming
We define f[i][k] to be true if and only if it is possible to reach stone i with last jump of size k. Initially f[0][0] = true, and all other elements of f are false.
We can determine the value of f[i][k] for all i and k using a double loop. For each possible jump size k, we look at the stones we could have jumped from: i-k, i-k+1, i-k+2. If any of these stones exist and if we can reach them with a last jump of size k-1, k, or k+1, then we can reach stone i with a last jump of size k.
If we can reach the last stone, the answer is true. Otherwise, the answer is false.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the number of stones.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Hash Map | Time Complexity: O(n^2), where n is the number of stones. This accounts for the iteration over the stones and the potential steps from each stone. |
| DFS with Memoization | Time Complexity: O(n^2), potentially exploring all |
| Hash Table + Memoization | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Hash Map | O(n^2) | O(n^2) | General solution with iterative state propagation and fast hash lookups |
| DFS with Memoization | O(n^2) | O(n^2) | When modeling the problem as recursive state exploration with caching |
Video Solution
Frog jump | Dynamic Programming | Leetcode 403 | Detailed Explanation in Hindi With Code • Pepcoding • 27,467 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Frog Jump easy or hard?
How to solve Frog Jump in O(n)?
What is the best approach for Frog Jump?
Is Frog Jump asked at Google/Amazon/Meta?
What data structure is used in Frog Jump?
What is the time complexity of Frog Jump?
Frog Jump Python or Java solution approach?
Ready to solve this problem?
Practice Frog Jump with our built-in code editor and test cases.
Practice on FleetCode