I've been doing some Codility challenges lately and the MaxCounters challenge got me stumped:
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 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.
[...] The goal is to calculate the value of every counter after all operations.
Below is my solution in Python. I can't reach 100% on it even though I am pretty confident it is an O(n+m) complexity solution. Codility fails it and says its an O(n*m) complexity solution.
def solution(N, A): counter =  * N max_val = 0 for v in A: if v <= N and v >= 1: if counter[v-1] < max_val+1: counter[v-1] = max_val+1 else: counter[v-1] += 1 else: max_val = max(counter) for i in range(len(counter)): if counter[i] < max_val: counter[i] = max_val return counter