Problem

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?

Solution

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

Looks O(N)

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

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

$O(m)$the next O(n)

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

$O(m+n)$or O(max(n,m))

$O(max(n,m))$.

Take home message:

Ditch the O(N)

$O(N)$array initializer, it’s not worth it. Use 2 separate passes, like the other guy did.