MaxCounters solution

Question

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
 continue
 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?

• Peilonrayz: Are you legally allowed to relicense the other persons code to CC-BY-SA 3.0?
• Sidharth Samant: @TamoghnaChowdhury Ah! Okay, thank you! That makes sense. I did not know that the array initialization was O(N).
• Sidharth Samant: @Peilonrayz I honestly did not know about it. The code is posted in the comments, so everyone can see. And I'm not reusing bits and pieces of his code in mine.

Answer 1

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.