Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

        increase(X) - counter X is increased by 1,
        max counter - all counters are set to the maximum value of any counter.

A non-empty vector A of M integers is given. This vector represents consecutive operations:

        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
        if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and vector A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

    vector<int> solution(int N, vector<int> &A);

that, given an integer N and a non-empty vector A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result vector should be returned as a vector of integers.

For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

        N and M are integers within the range [1..100,000];
        each element of vector A is an integer within the range [1..N + 1].

Note:

From the question, "N counters" means N cells in the count vector.

This problem is in the chapter of Counting Elements. A typical counting elements problem has vector A from which a count vector is obtained, where the value of each index in the count vector is the number of occurrences of the index as value in the A vector. The A vector given above is:

    A = {3, 4, 4, 6, 1, 4, 4}

With that, the normal count vector becomes:

Which is also written as:

    count = {0, 1, 0, 1, 4, 0, 1}

However, that is not the result wanted. What is wanted as return vector, is the count vector,

    count = {3, 2, 2, 4, 2}

where there is no value for the index 0, and from the following conditions:

        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
        if A[K] = N + 1 then operation K is max counter.

        where K is the index variable, and "increase(X)" means increment (increase by 1) the value of the index, 
        X in the count vector. Remember that each value in the count vector is initialized to 0, at the start.

With the example data above, the maximum possible value in A has to be N, which is the length of the given A vector. For the above case N = 5.

There is a nuance in the naming of variables in this chapter. In algorithm, m normally refers to the maximum value in vector A and the length of the count vector. However, in this problem, m (actually uppercase m) refers to the length of vector A and N refers to the length of the counter and maximum possible value in A. The presence of N+1 as value in A, does not cause normal incrementing. Read on!

As the count vector is being developed, for the value, N + 1 = 6 in A, after N = 5, all the cell values in the count vector, should be made, the highest count cell value so far. This is the real trouble in this problem: how to come up with an algorithm that will avoid running through all the count cells, making each cell value, the highest counter cell value, so far.

The solution to this problem is approached in two ways: firstly the brute force approach that runs through all the count cells, making each cell value, the highest counter cell value, so far; and secondly, a smart approach that avoids running through all the counter cells, in order to make each cell value, the highest counter cell value, so far.

Brute Force Approach

The table that shows what is happening in the brute force approach is:

There are 5 counter cells and there are 4 removable extra operations. It should have been 5 operations, but there has to be at least one operation for making the cell 1 value, the latest maximum count so far (in this case, 2). The extra 4 removable operations are to make cell 2, cell 3, cell 4, and cell 5, the latest maximum count so far (in this case, 2). Possible code for this brute force approach is:

    #include <iostream> 
    #include <vector>
    using namespace std; 

    int prevMax = 0;

    void increase(int X, vector<int> &count) {
        count[X] += 1;
        if (count[X] > prevMax)
            prevMax = count[X];    //track previous maximum which started at 0
    }
    
    void maxCounter(int N, int prevMax, vector<int> &count) { 
        for (int X = 1; X <= N; X++) {
            count[X] = prevMax;
        }0
    }

    vector<int> solution(int N, vector<int> &A) {
        vector<int> count(N+1, 0);    //including the preceding redundant (convenience) 0
        int M = A.size();

        for (int K = 0; K < M; K++) {
            int X = A[K];
            if (1<=X && X<=N) {
                increase(X, count);
            }
            else if (X==N+1) 
                maxCounter(N, prevMax, count);
        }

        return count;
    }

    int main() 
    { 
        vector<int> A{3, 4, 4, 6, 1, 4, 4};

        vector<int> v = solution(5, A);

        cout << v[0] <<' '<< v[1] <<' '<< v[2] <<' '<< v[3] <<' '<< v[4] <<' '<< v[5] << endl;

        return 0; 
    } 

The reader should read through the program if he/she has not already done so. The output is:

    0 3 2 2 4 2

Unfortunately, this program has 6 counter cells, which are cell 0, cell 1, cell 2, cell 3, cell 4, and cell 5. Cell 0 should not be there, because of part of the instruction, "1 ≤ X ≤ N" where N = 5.

Well, the output of the given problem from app.codility.com/programmers is: [3, 2, 2, 4, 2]. So the candidate has to return the count vector without the preceding 0.

Candidate: Always present your solution and answer, the way the examiner expects or knows.

In order to return the count vector without the preceding 0, a count vector of N cells, instead of N+1 has to be created; and for each of its value, 1 is subtracted from the corresponding index. That is: counter 1 becomes counter 0; counter 2 becomes counter 1; counter 3 becomes counter 2; and so on. In other words, for the example in the problem above, the 5 counters of the count vector, become indexed (numbered) from index 0 to index 4, instead of from index 1 to index 5 with the preceding convenience 0. The preceding convenience 0 has to be omitted, in order to have a count vector of exactly 5 cells.

The code without the C++ main() function, becomes:

    #include <iostream> 
    #include <vector>
    using namespace std; 

    int prevMax = 0;

    void increase(int X, vector<int> &count) {
        count[X-1] += 1;
        if (count[X-1] > prevMax)
            prevMax = count[X-1];
    }
    
    void maxCounter(int N, int prevMax, vector<int> &count) { 
        for (int X = 0; X < N; X++) {
            count[X] = prevMax;
        }
    }

    vector<int> solution(int N, vector<int> &A) {
        vector<int> count(N, 0);
        int M = A.size();

        for (int K = 0; K < M; K++) {
            int X = A[K];
            if (1<=X && X<=N) {    //X cannot be 0 (given)
                increase(X, count);
            }
            else if (X==N+1) 
                maxCounter(N, prevMax, count);
        }

        return count;
    }

The output is now,

    3 2 2 4 2

and same as from app.codility.com/programmers. The for-loop in the maxCounter() function, was also changed from "(int X = 1; X <= N; X++)" to "(int X = 0; X < N; X++)" but its body statement was not changed. In the C++ main() function, the expression, " <<' '<< v[5]" was removed. The reader should read the above two codes, and make the comparison, if he/she has not already done so.

There are three (non main) functions in the program. The maxCounter() function is the one that produces the removable extra operations. This function must be eliminated.

The second solution looks good, but at app.codility.com/programmers, the result for that is:

    Task score : 66% -  Correctness : 100% ; Performance : 40%
    Detected time complexity : O(MxN)

This (66%) is not good enough. What app.codility.com/programmers wants is O(N + M) time complexity. If M is 7 = 6+1 and N is 5 as above, then O(N x M) = O(7 x 5) = O(35) number of operations. What app.codility.com/programmers wants is O(N + M) = O(7 + 5) = O(12) number of operations. The number of operations to initialize all the elements of the count vector, just after creation, is not included in the expected time complexity.

A normal function, solution(), in the topic of Counting Elements, should result in a time complexity of O(M + N), where M in this case is the number of elements in vector, A and N is the number of cells (counters) in the count vector. O(M + N) roughly means, scanning vector A once in M time, and then scanning the count vector, once in an additional (plus) N time.

A time complexity of O(M x N) means that, at the limit, for each value, A[K], the count vector is scanned completely in N operations. In the above code, this repeated scanning is coming from the for-loop of the maxCounter() function. If the for-loop of the maxCounter() function can be reduced from xN to x1, then the time complexity of the code will go from O(N x M) to O(N + M).

What app.codility.com/programmers wants for O(M + N), is M number of operations to scan the given vector, A, fitting in the appropriate "number of occurrences" as values in the count vector, using the values of the given vector as indexes for the count vector; and additional N number of operations to "read" through the count vector.

Smart Approach

For the smart approach, the table that represents the number of operations, for the above given example, is:

At the start of the principal algorithm, there is a min and max variable, each with value 0. For each "A[K] = X" for the index of vector A, the counter cell, whose value is X, is incremented. If the cell value for the increment is the maximum value so far, then max becomes that value, while min remains at it previous value.

When A[K] = N + 1, and precisely A[3] = 6, max = 2, while still momentary, min = 0. Instead of making all the counter cells, 2, and wasting 4 operations, in one operation, min is then made 2 and max is made 2, saving (economizing) 4 operations.

From then onward, for any "A[K] = X" operation encountered, the counter cell, whose value is X, is incremented (by 1) and 2 is also added to the cell value. If the cell value for the increment is the maximum value so far, then max becomes that value (3 in this case), while min remains at it previous value (2 in this case). Precisely, at A[4] = 1 counter cell 1 becomes 3 and max becomes 3; counter cell 2 remains at 0, which should have been 2; counter cell 3 remains at 1, which should have been 2; counter cell 4 remains at 2, and that is alright because it was the previous max; and counter cell 5 remains at 0, which should have been 2.

At A[5] = 4 counter cell 1 remains at 3, and it is above 2; counter cell 2 remains at 0, which should have been 2, counter cell 3 remains at 1, which should have been 2, counter cell 4 increments to 3, but max remains at 3 from previous operation; and counter cell 5 remains at 0, which should have been 2 (the latest min).

At A[6] = 4 counter cell 1 remains at 3, and it is above 2; counter cell 2 remains at 0, which should have been 2, counter cell 3 remains at 1, which should have been 2, counter cell 4 increments to 4, and the new max becomes 4; and counter cell 5 remains at 0, which should have been 2 (the latest min).

The length of vector A ends at index 6. So the output has to be made. The last line of the above table at index 6 cannot be returned, because some values that are supposed to be at the new min, 2, are still below 2.

An extra N operations have to be made, to make all the counter cells, whose values are less than 2, to be 2. If that is done, the output will be:

    0 3 2 2 4 2

Again, the issue of the unwanted preceding 0! To solve this problem, assign the cell value of counter index 1 to index 0, counter index 2 to index 1, index 3 to index 2, index 4 to index 3, and index 5 to index 4. The following table illustrates this (at the first full row):

The return vector (output) is now correct, as:

    3 2 2 4 2

Generally, each time "A[K] = N + 1" is encountered, for the index of vector A, the value of min becomes the highest value so far, and the value of max also becomes the same highest value so far. There after, the value of max continues to increase with each operation, until "A[K] = N + 1" is encountered again. There is only one case for "A[K] = N + 1" above, with max = 2 = min. There can be more than one case. There can be more than one case, with for example, max = 7 = min, max = 10 = min, max = 14 = min, and so on.

And the ultimate code is:

    #include <iostream> 
    #include <vector>
    using namespace std; 

    vector<int> solution(int N, vector<int> &A) {
        vector<int> count(N, 0);
        int min = 0; 
        int max = 0; 
        int M = A.size();

        for (int K = 0; K < M; K++) {
            if (A[K]>=1 && A[K]<=N) {    //given
                if(count[A[K]-1] < min)
                    count[A[K]-1] = min+1;    //for vertically trailing counter after max memorized
                else
                    count[A[K]-1]++;    //for counter with last maximum value
                
                if(count[A[K]-1] > max)
                    max = count[A[K]-1];    //memorize latest maximum value for all future counters
            }
            else if (A[K]==N+1) 
                min = max;    //memorize latest minimum, which is same as latest maximum
        }

        for (int X = 0; X < N; X++) {  
            if (count[X] < min)    //if any counter value is less than latest minimum before read-out, after last maximum effect of A[K] = N + 1,
                count[X] = min;    //no counter cell should be less than latest minimum
        }

        return count;
    }

    int main() 
    { 
        vector<int> A{3, 4, 4, 6, 1, 4, 4};

        vector<int> v = solution(5, A);

        cout << v[0] <<' '<< v[1] <<' '<< v[2] <<' '<< v[3] <<' '<< v[4] <<' '<< v[5] << endl;

        return 0; 
    } 

The result from app.codility.com/programmers for this solution() function is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(N+M)

Conclusion

The reader must read this conclusion: With the smart (last) solution, when a counter is addressed based on a value in vector A, the counter is normally incremented by 1. However, when the value of N+1 is reached in A, the maximum value among all the counters is remembered. This maximum value is also the new minimum value moving forward. When any counter is to be addressed again, if its value is less than this minimum value, the value is made this minimum value, and at the same time incremented by 1 (i.e. min+1). If the counter is the one with the maximum value, its value is simply increased by 1. The incrementation of any counter addressed, continues until a value of N+1 is reached again in A; and the "cycle" repeats from there. All that is done in one for-loop.

The outputs from all the counters are required, just after the end of the vector A is reached. When that point is reached, a second and last for-loop in the solution() function, goes through the count vector, and if the value of any counter is below the latest minimum value, it makes it that minimum value. The reader should remember that when the value of N+1 is reached in A, all counters are supposed to be made the maximum value (which is the new minimum value).

The reader should read through the last code presented above again, in order to appreciate this conclusion.

The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.