MaxCounters Codility Challenge 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 = [0] * N
    max_val = 0

    for v in A:

        if v &lt;= N and v &gt;= 1:
            if counter[v-1] &lt; 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] &lt; max_val:
            counter[i] = max_val

    return counter
A couple of hints, to avoid spoiling the problem.

Hint 1


   What would happen if every entry in A were N + 1?


Hint 2


   What is the complexity of max(counter)?