Comment on page
Fastest Frog Jump
A small frog wants to get to the other side of a pond. The frog is initially located on one bank of the pond(position 0) and wants to get to the other bank(position X). The frog can jump any (integer) distance between 1 and D. If X > D then the frog cannot jump right across the pond. Luckily, there are leaves failing from a tree onto the surface of the pond, and the frog can jump onto the leaves.
You are given a zero-indexed array A consisting of N integers. This array represents failing leaves. Initially there are no leaves. A[K] represents the position where a leaf will fall in second K.
The goal is to find the earliest time when the frog can get to the other side of the
pond. The frog can jump from and to positions 0 and X(the banks of the pond) and
every position with a leaf.
For example, you are given integers X = 7, D = 3 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 5
Initially, the frog cannot jump cross the pond in a single jump. However, in second 3, after a leaf falls at position 4, it becomes possible for the frog to cross. This is the
earliest moment when the frog can jump across the pond(by jumps of length 1, 3 and 3)
Write a function:
int solution(int A[], int N, int X, int D);
that, given a zero-indexed array A consisting of N integers, and integers X and D, returns the earliest time when frog can jump to the other side of the pond. If the frog can leap across the pond in just one jump, the function should return 0. If the frog can get to the other side of the pond just after the very first leaf fails, the function should also return 0. If the frog is never able to jump to the other side of the pond, the function should return -1.
The Idea: I've heavily commented the code belong. The general idea is to have the frog just continually take whatever leaf it possibly can until of course, it can reach the end.
Complexity: O(nlogn) time and O(n) space. Consider the labeled worse case example below.
import queue
def fastest_frog_jump(leaf_times, jump_len, target):
# if the frog can jump across in one jump
if jump_len >= target:
return 0
# if the frog cannot jump across
if jump_len == 0 or not leaf_times:
return -1
# datastructure to contain the positions of the leafs
pq = queue.PriorityQueue()
frog_pos = 0
for time, leaf_loc in enumerate(leaf_times):
# check if the frog is currently within reach of target
if frog_pos + jump_len >= target:
return time
# if the leaf falls somewhere out in front of the frog,
# and whether or not it can current take the leaf or not
# will put it in the pq, and have it work it out
# it may be that the frog cannot take the leaf but in the
# future the leaf may be useful
if leaf_loc > frog_pos:
pq.put(leaf_loc)
# otherwise the leaf gets put behind the frog, in which case
# it can safely be ignored (it isn't getting us any closer)
# now just continue jumping on the next leaf, as far as
# the frog can
while not pq.empty():
# these leafs must be in front of the frog (always)
# careful to not actually remove from the pq till jump
closest_leaf = pq.queue[0]
if frog_pos + jump_len >= closest_leaf:
frog_pos = closest_leaf
# remove it from the queue since the
# frog was able to jump to it
pq.get()
# check if we can get to the end
if frog_pos + jump_len >= target:
return time
# otherwise we cannot jump to the closest leaf
else:
break
# at this point the frog cannot jump across
return -1
# note: time begins at 0
print(fastest_frog_jump([1,5,3,5,5,5], 2, 7)) # 2
print(fastest_frog_jump([2,1,0,1,2,3], 1, 4)) # 5
print(fastest_frog_jump([2,1,0,1,2,3], 1, 5)) # -1
print(fastest_frog_jump([6,5,4,3,2,1], 1, 7)) # 5 # (worst-case example)
print(fastest_frog_jump([1,3,1,4,2,5], 3, 7)) # 3
print(fastest_frog_jump([1,2,3,4,5,6], 1, 7)) # 5
Last modified 4yr ago