# Codility MaxCounters peformance in Python capping out at 77% performance

My problem is quite similar to the question found here, except I am attempting to answer the question in Python.

Given an array of N counters, all initialized to 0, and an array A representing a series of operations, find the final state of the counters. Each entry in A should be interpreted as follows:

• If 1 ≤ A[k]N, then increase the counter at A[k] by 1.
• If A[k] = N + 1, then set all counters to current maximum value.
def solution(N, A):
# write your code in Python 2.7
counters =  * N
max_count = 0
for x in A:
if 1 <= x and x <= N:
counters[x-1] += 1
if counters[x-1] > max_count:
max_count += 1
else:
counters = [max_count] * N
return counters


Nothing I can come up with allows me to do this in $O(N + M)$ time. I get rid of any max() functions going through the list by keeping track of it, but for the life of me I don't know how one is supposed to update N different variables M times (worst case scenario) without it being $O(N * M)$.

I am asking this question because I am uncertain what this question even asks is possible without having N processors to bring the $O(N)$ by itself stage of updating the counter array down to $O(1)$ through parallelization. Since the other question hasn't been answered, I guess what I want to know is if there is a data structure or some other heuristic that will get this down to $O(M + N)$.

• The code basically uses a dictionary object to keep a running histogram between occurrences of an entry of N+1, then updating counter only when the max_counter operation is applied. After the last max_counter operation, it just uses the naive approach. Quite ingenious, actually. Nov 18, 2014 at 3:18
• Duplicate? How about fizzbuzz? ;) Nov 18, 2014 at 3:37
• @ optical_anathema: yes, the dictionary idea is what I hinted at as M * log(M) and it was my first approximation; then I realised that a small constant amount of extra work per increment would work as well: counters[x-1] = max(counters[x-1], last_max_count) + 1 which gets rid of the log(M) of the dictionary search. That's the same as bainikolaus' code on that page, and I don't think it can be improved in any way except for renaming m and minValue. Nov 18, 2014 at 3:51
• Which solution is faster depends on the sizes involved: small M compared to biiig N, or the other way around. I bet that Codility have at least one biiig N case for flushing out naive algorithms, and this slightly favours the map (dictionary) approach. In languages like C/C++ the max() operation is virtually free (CMOV), and the last_max_count method is much leaner overall, meaning the map<> method is not competitive in C++. That's also one reason why it is hard to think fruitfully about optimisation without having some hard facts and good bounds on the sizes involved. Nov 18, 2014 at 4:03
• P.S.: perhaps the difference becomes clearer if I point out that the counter array already is one big bleeding frequency counter. Using a map/dictionary on the sequences between 'max_count fillings' only introduces an additional log(M) cost for the search. For gigantic input sizes the map/dictionary would again win because of locality of access compared to a huge, sparse counter array that is too big for any of the CPU caches. Nov 18, 2014 at 4:17

What hurts your performance is filling the array with max_count. So don't do it. Imply it. The trick is all there, and it makes this slightly different from trying to execute a literal transcription of the problem.