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.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.
JavaScript
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.
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.
Java
Time Complexity: O(n^2), potentially exploring all jump states for each stone.
Space Complexity: O(n^2), maintaining memoization of states.
| 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 |
DP 3. Frog Jump | Dynamic Programming | Learn to write 1D DP • take U forward • 691,535 views views
Watch 9 more video solutions →Practice Frog Jump with our built-in code editor and test cases.
Practice on FleetCode