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.

  • sandip

    [Tested Correction 100%, Performance 60% – 2 Perfromance Test Failing on large extreme counter N ]
    Can anyone please help me on cause?

    vector solution(int N, vector &A) {
    // write your code in C++14 (g++ 6.2.0)
    size_t sz = A.size();

    vector counters(N,0);
    int X;
    int maxCounterVal=0;
    for(size_t i = 0; i = 1 && X maxCounterVal)
    maxCounterVal = counters[X-1];
    }
    else if ( X == N+1 )
    {
    fill(counters.begin(),counters.end(),maxCounterVal);
    //counters.clear();
    //counters.resize(N,maxCounterVal);
    }
    }
    return counters;
    }

    • Your solution iterates over the vector too many times. (see the fill call which touches every element). Look at my proposed solution and try to understand how last_increase prevents the algorithm from touching all elements too often.

  • Ejiro Urhiafe

    I got 100% for correctness but 60% for performance. Any suggestions?

    import java.util.*

    class Solution {
    public static int[] solution(int N, int[] A) {
    int[] returnArray = new int[N];
    int max = 0;

    for (int i = 0; i < A.length; i++){
    if (A[i] = 1 ){
    returnArray[A[i]-1] +=1;
    if ((returnArray[A[i]-1]) > max){
    max = returnArray[A[i]-1];
    }
    }
    if (A[i] == N+1){
    Arrays.fill(returnArray, max);
    }
    }
    return returnArray;
    }
    }

    • remario richards

      because Arrays.fill is linear in time complexity , so its quadratic or m * n and not n + m

  • Alper Aykac

    %100 correctness %100 performance in java

    class Solution {
    public int[] solution(int N, int[] A) {
    int[] counters = new int[N];
    int idx = 0, max = 0, tmp = 0;
    for (int i : A) {
    if (i >= 1 && i tmp ? max : tmp;
    counters[i-1] = tmp;
    } else if (i == (N + 1)) {
    if(N >1) {
    counters[0] = max;
    counters[1] = max;
    for (int x = 1; x < N; x +=x) {
    System.arraycopy(counters, 0, counters, x, ((N – x) < x) ? (N – x) : x);
    }
    } else {
    counters[0]= max;
    }
    }
    }
    return counters;

    }
    }

    https://uploads.disquscdn.com/images/826283c4b45d5285f720c9650198ad42c17579e5aa2c32cb5dbaca311cc28798.jpg

    • M. Rahil Rafiq

      Hi;
      I could not understand the problem, can anyone explain how did this output generated in question.

      For example, given integer N = 5 and array 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)

  • Israel

    Thanks for the post, I had performance issue, and got the idea from your code.
    here is my solutiuon:

    # solution #1 Python
    # you can write to stdout for debugging purposes, e.g.
    # print(“this is a debug message”)

    def solution(N, A):
    B = [0] * N

    cur_max = 0
    last_upd_max = 0

    for a in A:
    if a > N:
    last_upd_max = cur_max
    if a <= N:
    if B[a-1] < last_upd_max:
    B[a-1] = last_upd_max
    B[a-1]+=1
    if cur_max < B[a-1]:
    cur_max = B[a-1]

    for i in range(0,len(B)):
    if B[i] < last_upd_max:
    B[i] = last_upd_max

    return B

    // solution #2 C – assume Struct Result with C = int*, L = int
    // you can write to stdout for debugging purposes, e.g.
    // printf("this is a debug messagen");

    struct Results solution(int N, int A[], int M) {

    struct Results result;
    result.C = (int*)calloc(N, sizeof(int));

    int cur_max = 0;
    int last_upd_max = 0;

    for(int i=0; iN)
    last_upd_max = cur_max;
    else
    {
    result.C[A[i]-1] = last_upd_max > result.C[A[i]-1] ? last_upd_max : result.C[A[i]-1];
    result.C[A[i]-1]++;
    if(cur_max<result.C[A[i]-1])
    cur_max=result.C[A[i]-1];
    }
    }

    for(int i=0; i<N; i++)
    {
    if(result.C[i] < last_upd_max)
    result.C[i] = last_upd_max;
    }

    result.L = N;

    return result;
    }