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

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.

• Zakir Dakua

Oh, Good!

• I guess that this post helped?

• Zakir Dakua

Yes, and the trick is 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.
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 ]

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;

}
}

• 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;
}

• glad to have helped you out ðŸ™‚