FrogRiverOne at app.codility.com-programmers in C Plus Plus Explained - Find the earliest time when a frog can jump to the other side of a river.
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 24 Jan 2024
Task
Detected time complexity : O(n)
Lesson 4 at app.codility.com/programmers
The solution and its explanation are given in this article.
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 a vector 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.
For example, you are given integer X = 5 and vector 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.
Write a function:
int solution(int X, vector<int> &A);
that, given a non-empty vector 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.
For example, given X = 5 and vector 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
the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and X are integers within the range [1..100,000];
- each element of vector A is an integer within the range [1..X].
Note:
The frog jumps from one leaf to the next leaf. As time clocks, the leaves fall on a straight line, but not necessarily in ascending position order of 1, 2, 3, etc. They fall in some disorder as the given vector shows. Since the frog will only begin crossing, when all the positions to have leaves, have leaves (more than one leave at a position is possible), then the earliest time is when all the positions have leaves. The frog should start crossing at this earliest time.
So the earliest time depends on the given vector. If a given vector does not have all the positions across the river with at least one leaf, then the frog will never cross. Since some positions across the river can have zero leaf, and others, far more than 1 leaf, the number of elements of the given array can be far more than the number of positions across the river (1 to X, inclusive).
The lesson for this problem is Counting Elements. The candidate should expect that the solution to this problem, needs a count vector. That makes two vectors: the given and the count vector!
Also, at the end of the problem description, it is said that the maximum element in the given vector is X. This is a strong indication that there is need for a count vector from 0 to X+1.
Part of the problem reads, “. . . A consisting of N integers representing the falling leaves.” The candidate has to understand this as “fallen leaves”; that is, the leaves have already fallen and stopped, by the time the question is asked; and that is why the amount of fallen leaves are in a complete array (vector).
There are four varying quantities in the problem, which are the time, position of fallen leaves across the river, the number of leaves per position, and the vector (given array) index. It should also be understood that the positions are whole numbers (integers).
Note: the total number of seconds taken is the number of elements in the array, but the candidate is advised to apply zero based indexing.
Strategy
There is an issue with the vector index positions and the number of seconds elapsed. It is said in the problem, that at second 6, a leaf falls in position 5. Is it supposed to be, that at second 8, a leaf falls in position 5, since the total number of seconds is the length of the array? - Answer: a leaf falls in position 5 at second six; and after the frog has started crossing, leaves would continue to fall in different positions, making the given array longer. Yes, in second 6 a leaf falls at position 5.
Candidate: Whenever a question or problem is asked, give your answer the way the examiners want, even if you think that there is an issue (such as above) with the problem.
The table for the given vector (array) is:
| Position | 1 | 3 | 1 | 4 | 2 | 3 | 5 | 4 |
| Array index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
The given array or table must be interpreted as follows: In second 0, one leaf falls at position 1; in second 1 one leaf falls at position 3; in second 2, one leaf falls at position 1 again (making two leaves at position 1); in second 3 one leaf falls at position 4; in second 4, one leaf falls at position 2; in second 5 one leaf falls at position 3 (making two leaves at position 3). Note that after 5+1 = 6 seconds, not all the positions across the river have leaves. Position 5 in particular, does not have any leaf yet, while the rest of the positions (1 to 4, inclusive) have at least one leaf.
In second 6 one leaf falls at position 5, making all the 5 positions have leaves. At least one leaf is necessary at a position to enable the frog step onto that position. Assume that leaves have no weight so as to sink into the river, when more than one leaf is at a position. In second 7, one leaf falls at position 4 (making two leaves at position 4). This second leaf at position 4 is redundant, because by this time, all the positions across the river have leaves, and the frog has already started leaping (jumping). Assume that all the positions with leaves are on a straight line. How long the frog takes to cross the river is not of concern in this problem.
For the count vector, using the above given vector (array), count the number of occurrences of each element (value) in the given vector, and put each against its value, as follows:
| No. of leaves | 0 | 2 | 1 | 2 | 2 | 1 |
| Position | 0 | 1 | 2 | 3 | 4 | 5 |
So, if in the count vector, each element (number of leaves) is greater than 0, from position 1 to X = 5, then the frog can start jumping from one leaf to the next. With such setup, the algorithm function should return the second (index) in the given vector (array), where a leaf fell, for all positions to have at least one leaf. So the function needs to have some form of counter which is counting the number of positions that have at least one leaf, as the leaves are falling. When this counter reaches X=5, the function returns the corresponding index (second) in the given array.
If by the given vector (array), any of the elements in the count vector (array) remains at 0, within 1 and X (inclusive), then the frog will never start to cross (and never cross) the river. With such setup, the algorithm function should return -1. This means that the counter counting the number of positions that have at least one leaf, will never be 5 in the function.
At app.codility.com/programmers, the time taken to produce the count vector, of all zero values, is ignored, when quoting the overall time complexity, of the solution() function. There, the time complexity is given as O(n), for the solution() function below.
Tentative O(n+m) Time Solution
Here, the count vector will be scanned to see if all the indexes from 1 to X have number of leaves greater than 0. For any index with value zero, the scanning should stop and -1 returned. Such scanning should take place after all the increments (number of occurrences) of the values of the count vector have been made. If all the values for the indexes of the count vector are greater than zero (which means the frog can start crossing), then the program has to somehow obtain the index in the given vector at which the number of positions across the river just became X (=5). This looks impossible for the following reason:
The count vector is a mapping from the given vector of which the indexes of the given vector are lost, because the number of occurrences of the same value in the given vector becomes one element value in the count vector and the value itself from the given vector, becomes an index of the count vector.
So, there is a problem here: while scanning the count vector, it is not straightforward to know when all the positions across the river (count > 0) have been encountered. There is a solution to this problem, which actually makes the algorithm O(n) time. In life there are few solutions like this, that come with improvement. The solution is that, as the values of the given vector are being scanned and the number of occurrences of each value being put (incremented) into the count vector, the number of positions which have at least one leaf are counted. As soon as that number is equal to X (=5 in this problem), the index (seconds) of the given vector is returned. That index is the answer. This takes a maximum of n time for scanning the given vector.
Coding the solution is actually simple: before incrementing the value of an index, which represents a position across the river in the count vector, check if the value of the index is 0. If it is 0, and therefore about to be incremented, then that is a position with at least one leaf. At that point, the counter variable (such as allPositions \96 see code below) for the positions with at least one leaf, is incremented. Incrementing this counter variable, allPositions is different from incrementing the values of the count vector. This counter variable is incremented only once for each index of the count vector, while some values of the count vector are incremented more than once as expected.
Again, in life when you get stuck, the solution if at all exists, usually comes with no advantage or some disadvantage. Hardly does the solution come with advantage like this one (decreasing time complexity, and just needs common sense to code or implement).
O(n) Time Complexity
#include <iostream>
#include <vector>
using namespace std;
int solution(int X, vector<int> &A) {
int N = A.size();
vector<int> count(X+1, 0); //Create and make all count elements 0. This O(m) time is ignored at app.codility.com/programmers
int allPositions = 0; //for counting from 1 to X
for(int i=0;i<N;i++){
if (count[A[i]] == 0){ //then it must be incremented, so add it now to allPositions
allPositions++;
count[A[i]] = count[A[i]] + 1;
if (allPositions == X)
return i;
}
}
return -1; // when allPositions end up < X after complete scanning of given vector
}
int main()
{
vector<int> B{1, 3, 1, 4, 2, 3, 5, 4};
int num = solution(5, B);
cout << num << endl;
return 0;
}
Conclusion
If in the count vector, each element (number of leaves) is greater than 0, from position 1 to X = 5, then the frog can start jumping from leaf to leaf. If by the given vector, any of the elements in the count vector remains at 0, within 1 and X (inclusive), then the frog will never start to cross (and never cross).
The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.