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 = *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
*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 =  * 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?