The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

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.

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.

Write a function:

    int solution(int X, int 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.

For example, given 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

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 array A is an integer within the range [1..X].

Use frequency-of-occurrences-array, but do it in O(n) time.

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; though there are 8 seconds altogether.

The frog will jump 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 array 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, just after second 6 above, and not after second 7 or 8, if 8 or more seconds were allowed.

So the earliest time depends on the given array. If a given array 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 array (frequency-of-occurrences-array). That makes two arrays: the given and the count array!

Also, at the end of the problem description (assumptions), it is said that the maximum element in the given array is X. This is a strong indication that there is need for a count array 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 (that is, by the time the frog has to start hopping); and that is why the amount of fallen leaves are in a complete array. However, the frog does not have to wait for all the leaves to fall before it starts hopping. The frog has to start hopping when all the positions from 1 to X (inclusive), each has at least one leaf, while the leaves may continue falling.

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 array (given array) index. It should also be understood that the positions are whole numbers (integers). The array indexes and the seconds, are the same things; so there are effectively three varying quantities.

Again: the total number of seconds taken is the number of elements in the array, but the candidate is advised to apply zero based indexing for the positions (first bank is 0 and last bank is X+1).

Strategy

The length of the given array is the number of seconds. 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.

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 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, but 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 on any leaf (pile of leaves). 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 array, using the above given array, count the number of occurrences of each element (value) in the given array, and put each against its value, as follows:

The positions here are the indexes for the count array. X+1 = 5+1 has not been included. It does not have to be included. This count array is the number of leaves per position (occurrences), across the river. Note that the length of the count array is less than the length of the given array, for this problem. m = X = 5, and so the length of the count array is 5 + 1 = 6 (for the convenience zero). The length of the given array is 8.

So, if in the count array, 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 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 array, any of the elements in the count 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.

O(n) Time Solution

Observe from above that, what matters in the count array is whether a value is greater than zero or is zero. Would it not have been better to have the count array of just True or False, with False for 0 and True for greater than zero? - Yes, it is better that way, where False means no leaf fell at that position and True means at least one leaf fell at that position. With that, the count array becomes Boolean, and it is:

As the algorithm iterates over the given array for the first time, this count array of true and false is produced. For the same index, true can be written more than once, for frequency of more than 1, accordingly.

When the count array is produced the first time, all its elements are initialized to false. Now, as the algorithm iterates over the given array for the first time, to produce the corresponding trues, the counter is incremented for each true produced in a new cell (and not for the same cell, where it can be made more than once). In order to know whether a count cell is a new cell, its value still has to be false (from initialization).

The counter starts from 1 to X=5. As soon as the counter reaches X=5, the index (number of second intervals) of the given array is returned. The name of the counter in the following program is, allPositions.

The program is (read through the code and comments):

#include <stdio.h>
#include <stdbool.h>

int FrogRiverOne(int A[], int X, int n) {
    bool count[X+1];    //X is m
    for (int i=0; i < X+1; i++)
        count[i] = false;    //initializing count array

    int allPositions = 0;  //for counting from 1 to X
    
    for(int i=0; i < n; i++){
        if (count[A[i]] == false){    //then it must be incremented, so add it now to allPositions
            allPositions++;
            count[A[i]] = true;
            if (allPositions == X)
                return i;
        }
    }
    return -1;  // when allPositions end up < X after complete scanning of given array
}
  
int main(int argc, char **argv) 
{
    int A[] = {1, 3, 1, 4, 2, 3, 5, 4};
    int n = sizeof(A) / sizeof(A[0]);    //length of given array
    int X = 5;    //X is m, for max number in A
            
    int num = FrogRiverOne(A, X, n);
    printf("%i\n", num);
    
    return 0; 
}

The time complexity of the called function is O(n), where n is the length of the given array. This is because the count array is never iterated over, and the given array is iterated over, only once. The time to initialize the count array elements to false is ignored. Note that, though the count array was not iterated over, it is still needed in the algorithm.

The space complexity is O(n+m), with n being for the given array and m being for the count array. The space for the allPositions variable and any temporary variable is ignored.

Thanks for reading.