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] == 0stones is sorted in a strictly increasing order.The key challenge in #403 Frog Jump is determining whether a frog can reach the final stone when each jump depends on the previous jump length. The frog starts with a jump of 1 unit, and if the last jump was k, the next jump can be k-1, k, or k+1. A common and efficient strategy is to use dynamic programming with hash-based lookup.
Create a mapping from each stone position to the set of jump lengths that can land on it. When the frog reaches a stone with jump k, you attempt the next possible jumps (k-1, k, k+1) and check whether a stone exists at the resulting position. If it does, store the new jump length for that stone. This approach efficiently tracks reachable states while avoiding repeated exploration.
By using fast lookups and storing reachable jump sizes per stone, the algorithm systematically explores valid paths until either the final stone becomes reachable or all possibilities are exhausted.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Hash Map / Hash Set | O(n^2) | O(n^2) |
take U forward
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.
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.
1def canCross(stones):
2 if stones[1] != 1:
3 return False
4 stone_dict = {stone: set() for stone in stones}
5 stone_dict[0].add(1)
6 for stone in stones:
7 for jump_length in stone_dict[stone]:
8 for step in [jump_length - 1, jump_length, jump_length + 1]:
9 if step > 0 and (stone + step) in stone_dict:
10 stone_dict[stone + step].add(step)
11 return len(stone_dict[stones[-1]]) > 0The 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.
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.
Time Complexity: O(n^2), potentially exploring all jump states for each stone.
Space Complexity: O(n^2), maintaining memoization of states.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4using namespace std;
5
class Solution {
public:
bool canCross(vector<int>& stones) {
unordered_map<int, unordered_set<int>> memo;
return dfs(stones, 0, 0, memo);
}
private:
bool dfs(vector<int>& stones, int idx, int jump, unordered_map<int, unordered_set<int>>& memo) {
if (idx == stones.size() - 1) return true;
if (memo[stones[idx]].count(jump)) return false;
for (int j = jump - 1; j <= jump + 1; ++j) {
if (j > 0) {
int next_pos = stones[idx] + j;
auto it = lower_bound(stones.begin(), stones.end(), next_pos);
if (it != stones.end() && *it == next_pos) {
int next_idx = it - stones.begin();
if (dfs(stones, next_idx, j, memo)) return true;
}
}
}
memo[stones[idx]].insert(jump);
return false;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Frog Jump is considered a classic hard dynamic programming problem and has appeared in interviews at top tech companies. It tests problem decomposition, state tracking, and efficient use of hash-based data structures.
Yes, Frog Jump is commonly solved using dynamic programming. The DP state tracks which jump lengths can reach each stone, allowing the algorithm to build solutions incrementally from previous states.
The optimal approach uses dynamic programming combined with a hash map or hash set. For each stone, you store the jump sizes that can reach it and try the next possible jumps (k-1, k, k+1). This avoids redundant checks and efficiently explores valid paths.
Hash maps and hash sets work best because they allow constant-time lookups for stone positions and reachable jump sizes. Each stone maps to a set of jump lengths that can land there, enabling efficient state tracking.
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.