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.
For example:
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.
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.
Could you please implement a function that takes the list of stones as input and returns whether the frog can cross the river?
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.
A brute-force approach would involve exploring all possible jump combinations from each stone. This can be implemented using recursion.
k-1
, k
, and k+1
, where k
is the size of the last jump.true
.false
.This approach will likely result in a Time Limit Exceeded (TLE) error for larger inputs due to its exponential time complexity.
Code (Python):
def can_cross_brute_force(stones):
n = len(stones)
if n <= 1:
return True
def can_jump(index, jump_size):
if index == n - 1:
return True
for next_jump in [jump_size - 1, jump_size, jump_size + 1]:
if next_jump > 0:
next_stone = stones[index] + next_jump
if next_stone in stones:
next_index = stones.index(next_stone)
if can_jump(next_index, next_jump):
return True
return False
return can_jump(0, 1)
Time Complexity: O(3N), where N is the number of stones. For each stone, we explore up to 3 possible jumps.
Space Complexity: O(N) due to the recursion depth.
A more efficient solution involves using dynamic programming to avoid redundant calculations. We can use a hash map (dictionary in Python) to store the possible jump sizes for each stone.
k
, calculate the positions reachable with jumps k-1
, k
, and k+1
.true
. Otherwise, return false
.Code (Python):
def can_cross(stones):
n = len(stones)
if n <= 1:
return True
stone_jumps = {stone: set() for stone in stones}
stone_jumps[0].add(0)
for i in range(n):
stone = stones[i]
for jump_size in stone_jumps[stone]:
for next_jump in [jump_size - 1, jump_size, jump_size + 1]:
if next_jump > 0:
next_stone = stone + next_jump
if next_stone in stone_jumps:
stone_jumps[next_stone].add(next_jump)
return len(stone_jumps[stones[-1]]) > 0
Time Complexity: O(N2), where N is the number of stones. We iterate through each stone and, for each stone, iterate through its possible jump sizes.
Space Complexity: O(N), where N is the number of stones, to store the stone_jumps
hash map.
true
.The dynamic programming approach provides a more efficient solution compared to the brute-force method. It avoids redundant calculations by storing the possible jump sizes for each stone, resulting in a time complexity of O(N2) and a space complexity of O(N). Handling edge cases is crucial to ensure the correctness of the solution.