MaxCounters solution

Posted on


I am doing this Codility problem

You are given N counters, initially set to 0, and you have two possible operations on them:

  • increase(X) − counter X is increased by 1,
  • max counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

  • if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
  • if A[K] = N + 1 then operation K is max counter.

I have ended up with this code –

def solution(N, array):
    counters = [0]*N
    maximum = 0
    for a in array: # O(m) as array has m integers
        if a >=1 and a <= N:
            counters[a-1] += 1
            maximum = max(counters[a-1], maximum) 
        if a == N+1:
            counters = [maximum]*N
    return counters

I am failing two test cases because of timeout errors. I timed the function with array as [10]*100000 and N


as 9. It took 0.175681062359 seconds which is clearly not desirable. I do not understand where the time complexity increases. The for loop has O(M)


complexity because array has M


elements and even though max() has O(n)


complexity, that doesn’t matter since I’m comparing just two elements. I looked at a solution by Andrei Simionescu and it looks awfully similar to mine –

def solution(n, arr):
    out = [0] * n
    m = 0
    last = 0
    for op in arr:
        op -= 1 
        if op == n:
            last = m
        out[op] = max(out[op], last) + 1
        m = max(m, out[op])
    for i in xrange(n):
        out[i] = max(out[i], last)
    return out

I timed the above code and it took just 0.0276817503901 seconds on the same input. What is it that I’m doing wrong?


if a == N+1: 
     counters = [maximum]*N #array initializer

Looks O(N)


to me, making your total time complexity O(Nm)


worst case. The other guy has 2 separate loops, one O(m)


the next O(n)


, for a total time complexity of O(m+n)


or O(max(n,m))



Take home message:

Ditch the O(N)


array initializer, it’s not worth it. Use 2 separate passes, like the other guy did.

Leave a Reply

Your email address will not be published. Required fields are marked *