Codility ‘MaxCounters’ Solution

Short Problem Definition:

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Link

MaxCounters

Complexity:

expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N)

Execution:

The idea is to perform the specified operation as stated. It is not required to iterate over the whole array if a new value is set for all the values. Just save the value and check it when an increase on that position is performed.

Solution:
#include <algorithm>

vector<int> solution(int N, vector<int> &A) {
    vector<int> sol;
    int current_max = 0;
    int last_increase = 0;

    for(int i=0; i<N;i++){
        sol.push_back(0);
    }

    for(unsigned int i=0; i<A.size();i++){
        if (A[i] > N) {
            last_increase = current_max;
        } else {
            sol[A[i]-1] = max(sol[A[i]-1], last_increase);
            sol[A[i]-1]++;
            current_max = max(current_max, sol[A[i]-1]);
        }
    }

    for(int i=0; i<N;i++){
        sol[i] = max(sol[i], last_increase);
    }

    return sol;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Zakir Dakua

    Oh, Good!

  • Sean Janson

    Great solution, I couldn’t figure out the ‘last_increase’ trick, killing me on performance O(n*m). Anyway, I think your code has a tiny inaccuracy, the task description (at least in Java) states:
    if A[K] = N + 1 then operation K is max counter.
    your code handles
    if A[K] > N then operation K is max counter.

    • hmm, the C++ statement is also N+1, it passes all the tests so it must be equivalent as far as the examples go. If A[K] > N+1 -> the behaviour is unspecified.