Below is the Python solution to MaxCounters programming lesson in Codility. This gives the O(M+N) time complexity. The link to the question is here.
MaxCounters:
Calculate the values of counters after applying all alternating operations: increase counter by 1 and set value of all counters to current maximum
# Detected time complexity: O(N + M) %100 from codility
MaxCounters:
Calculate the values of counters after applying all alternating operations: increase counter by 1 and set value of all counters to current maximum
# Detected time complexity: O(N + M) %100 from codility
def solution(N,A): B=[0]*N baseValue =0; maxCount = 0; for x in A: if 1 <= x <= N: B[x-1] = max(B[x-1],baseValue) + 1 maxCount=max(B[x-1],maxCount) else: baseValue = maxCount for i in xrange(N): B[i]=max(B[i],baseValue) return B ;