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)\$.

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