This is the code I am using for the Codility lesson: MaxCounters
def solution(N, A): counters = [0] * N max_c = 0 for el in A: if el >= 1 and el N: counters = [max_c] * N return counters Every test passes but the last one ("all max_counter operations") times out after 7 seconds so the result is just 88% with time complexity of O(N+M).
Is it possible to improve the time complexity of the algorithm and get 100% test result using Python?
The MaxCounters task
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.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..N + 1].
Источник: https://stackoverflow.com/questions/588 ... s-using-py
