5
\$\begingroup\$

I am doing this Codility problem

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 zero-indexed 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.

I have ended up with this code -

def solution(N, array):
    counters = [0]*N
    maximum = 0
    for a in array: # O(m) as array has m integers
        if a >=1 and a <= N:
            counters[a-1] += 1
            maximum = max(counters[a-1], maximum) 
        if a == N+1:
            counters = [maximum]*N
    return counters

I am failing two test cases because of timeout errors. I timed the function with array as [10]*100000 and \$N\$ as 9. It took 0.175681062359 seconds which is clearly not desirable. I do not understand where the time complexity increases. The for loop has \$O(M)\$ complexity because array has \$M\$ elements and even though max() has \$O(n)\$ complexity, that doesn't matter since I'm comparing just two elements. I looked at a solution by Andrei Simionescu and it looks awfully similar to mine -

def solution(n, arr):
    out = [0] * n
    m = 0
    last = 0
    for op in arr:
        op -= 1 
        if op == n:
            last = m
            continue
        out[op] = max(out[op], last) + 1
        m = max(m, out[op])
    for i in xrange(n):
        out[i] = max(out[i], last)
    return out

I timed the above code and it took just 0.0276817503901 seconds on the same input. What is it that I'm doing wrong?

\$\endgroup\$
  • \$\begingroup\$ Are you legally allowed to relicense the other persons code to CC-BY-SA 3.0? \$\endgroup\$ – Peilonrayz Jan 3 '17 at 17:05
  • \$\begingroup\$ @TamoghnaChowdhury Ah! Okay, thank you! That makes sense. I did not know that the array initialization was O(N). \$\endgroup\$ – Sidharth Samant Jan 3 '17 at 17:22
  • \$\begingroup\$ @Peilonrayz I honestly did not know about it. The code is posted in the comments, so everyone can see. And I'm not reusing bits and pieces of his code in mine. \$\endgroup\$ – Sidharth Samant Jan 3 '17 at 17:24
4
\$\begingroup\$
if a == N+1: 
     counters = [maximum]*N #array initializer

Looks \$O(N)\$ to me, making your total time complexity \$O(Nm)\$ worst case. The other guy has 2 separate loops, one \$O(m)\$ the next \$O(n)\$, for a total time complexity of \$O(m+n)\$ or \$O(max(n,m))\$.

Take home message:

Ditch the \$O(N)\$ array initializer, it's not worth it. Use 2 separate passes, like the other guy did.

\$\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.