2
\$\begingroup\$

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 <= 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
\$\endgroup\$
2
\$\begingroup\$

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)?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.