Find the earliest time when a frog can jump to the other side of a river.
Problem
A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.
Write a function:
def solution(X, A)
that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.
Write an efficient algorithm for the following assumptions:
N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Example
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
Hint
To solve this problem, we will maintain two variables.
true_positions and count_true
true_positions: identifies the positions that have been covered by a leaf
count_true: counts the number of true we have accumulated in the true_positions list.
We will write a program to traverse the input array and keep updating these two variables (true_positions and count_true).
We will exit the program once count_true is equal to X.
Code
def solution(X, A):
true_positions = [False for i in range(X + 1)]
count_true = 0
for i in range(len(A)):
if true_positions[A[i]] == False:
true_positions[A[i]] = True
count_true += 1
if count_true == X:
return i
return -1
Test
Example test: (5, [1, 3, 1, 4, 2, 3, 5, 4])
OK
Detected time complexity:
O(N)
Test Cases
Correctness tests
simple test
single element
extreme_frog
frog never across the river
small_random1
3 random permutation, X = 50
small_random2
5 random permutation, X = 60
extreme_leaves
all leaves in the same place
Performance tests
medium_random
6 and 2 random permutations, X = ~5,000
medium_range
arithmetic sequences, X = 5,000
large_random
10 and 100 random permutation, X = ~10,000
large_permutation
permutation tests
large_range
arithmetic sequences, X = 30,000