Codility MaxCounters peformance in Python capping out at 77% performance

Question

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 = [0] * 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)\$.

• optical_anathema: 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.
• Mathieu Guindon: Duplicate? How about fizzbuzz? ;)
• DarthGizka: @ 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.
• DarthGizka: 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.
• DarthGizka: 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.

Answer 1

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.

Spelling out the details would rob pundits of the enjoyment of puzzling...

I don't know about Codility, but elsewhere the tasks can often be solved with efficient coding of a naive algorithm (especially in C/C++) instead of solving the puzzle algorithmically. Sometimes I try the 'raw firepower' solution as well, if it promises an interesting challenge. But only after finding the real solution, since each puzzle is basically about finding a specific trick that goes beyond the naive algorithm.

Given that people do these challenges for the puzzle value I think it would defeat their purpose if we posted complete solutions.

P.S.: the sketched solution reduces runtime only to M * log(M) + N or M * C + N but that should be sufficient (and enough of a hint).

• optical_anathema: I can't upvote (not enough reputation:), but you got it. Thank you for your input.