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 &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:

At second 0, a leaf falls at position 1. At second 1, a leaf falls at position 3. At second 2, a leaf falls at position 1 again (two leaves at position 1). At second 3, a leaf falls at position 4. At second 4, a leaf falls at position 2. At second 5, a leaf falls at position 3 again (two leaves at position 3). At second 6, a leaf falls at position 5. All positions now have at least one leaf, and the frog can start crossing. At second 7, a leaf falls at position 4 again (two leaves at position 4). However, the frog did not have to wait for the second leaf to fall at position 4, before it could start crossing. There are 8 seconds altogether. And the seconds do not correspond to positions. For example, second 0 has position 1, and second 1 has position 3.

The frog will jump from one leaf to the next leaf, just after all the positions have been filled with at least one 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 (assumptions), 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. Total number of seconds is the length of the vector, while total number of positions is X. There is 0 second, but position 0 is at the starting bank and does not corresponds to second 0. The frog can be at position 0 for a long time (many seconds) before second counting starts.

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, by the time the frog has to start hopping; 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). The vector indexes and the seconds, are the same things; so there are effectively three varying quantities.

Though the total number of seconds taken is the number of elements in the array, the candidate is advised to apply zero based indexing for the positions.

Strategy

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 with the problem.

The table for the given vector (array) is:

With the counting of the seconds beginning from 0, the indexes represent seconds, and not the positions across the river. From the given data, the positions across the river are from 1 to 5 (= X), with position 1 on the river, but near the starting bank, and position 5 on the river but near the ending bank (on the other side of the river). Position 0 is on ground at the starting bank, and position X+1 is also on ground at the ending bank.

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). Also assume that the frog cannot sink with any leaf. 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.

Bear in mind that each value in the given vector is a position (from 1 to X). 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:

The number of occurrences of a particular position in the given vector, is the number of leaves at that position. The positions in this table, are the indexes for the count vector. Position 0 has no leaf and should not have, because it is at the starting bank and not on the river. X+1 = 5+1 has not been included. It does not have to be included. This count vector is the number of leaves per position (occurrences), across the river. Note that the length of the count vector is less than the length of the given vector, for this problem. m = X = 5, and so the length of the count vector is 5 + 1 = 6. The length of the given vector is 8.

The table should also be interpreted as follows: Each index (above 0) is a position on the river and the number of occurrences per index, is the number of times that position (index) occurs in the given vector (receives a leaf).

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 seconds (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 (seconds) in the given array.

If by the given vector (array), 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 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 this solution() function. There, the time complexity is given as O(n), for the solution() function below.

Tentative O(n+m) Time Solution

In a typical O(n+m) solution, the given vector is scanned in n times, to put the number of occurrences of the elements of the given vector into the count vector. The count vector is then scanned in a maximum of m (X above) times to look for the answer.

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 (number of seconds just passed) in the given vector at which the number of positions across the river with leaves, 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 (shorter time). 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 different positions which have at least one leaf are counted. As soon as that number is equal to X (=5 in this problem), the index (same as seconds passed) of the given vector is returned. That index is the answer. This takes a maximum of n time for scanning the given vector.

If the number of positions with at least one leaf never reaches X, after the given vector has been scanned completely, then the frog cannot cross and -1 is returned. On the other hand, as soon as the couning of the number of positions with at least one leaf, reaches X, then the number of iterations so far, which is the number of seconds just passed, is returned.

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 becomes a position with at least one leaf. At that point, the counter variable (such as allPositions – 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 comes with 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

In the following program, the solution() function does work in O(n) time (read through the whole program and the comments):

#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.