Solution to Max-Counters by codility

19 Jan

Question: http://codility.com/demo/take-sample-test/max_counters

Question Name: MaxCounters

A straightforward solution is easy as following. But the expected worst-case time complexity cannot be guaranteed.

We could use lazy-write to improve the performance. When receiving the max_counter command, we record the current-max value, but do not change the list content. Only when we are going to return the list or increace a specific element, we will apply the stored value to the corresponding element(s).

64 Replies to “Solution to Max-Counters by codility

  1. java, 100%

    • First of all, thanks for sharing your solution. If some comments are there to help the readers, it would be much better.
      Your solution could pass all the test. But as far as I see, it does not have time complexity O(N+M), even though the Codilty system said so. The time complexity should be O(N*M), as new int[N] uses O(N).
      Essentially, your solution is an optimized version of my first solution. Actually it could be optimized further, as shown in https://codility.com/demo/results/demoDEYNRS-38A/ . This optimized Python solution uses less time in all test. ( Even though it is quicker, it failed in one test because of TIMEOUT ERROR. I do not know why, and I am trying to contact Codility.)

      • I guess the problem in this solution is this line: result = [maxVal]*N. This basically makes the solution a O(M*N), doesn’t it (a new array of N elements might be created in each loop iteration if the commands all increase the counter, maybe this is the reason of the failure)? Strange that codility accepts it as an O(M+N). Maybe array/list instantiation in python is somehow optimized so that it is faster than iterating over an old list and setting element?

        • Yes, I agree with you. It is O(M*N). Codility estimate the complexity. And no estimation in the world is perfectly accurate.

    • Just get the confirmation from Codility team. Your solution is not O(N+M). It passed the tests by chance, because:
      “Java has a substantial overhead to start the virtual machine. We use a bit more liberal timeouts for programs in Java” – From Codility Team

    • For my solution, inside the two for loops, there are only either comparison (if) or single cell assignment. So the two for loops are O(M) and O(N) respectively. Totally, it’s O(N+M).
      For your solution, in the first loop, there is a statement as “counters = new int[N];”, which is O(N). And the loop funs for M times. So it’s time complexity is O(N+M+N*number_of_max_counter_operations). In worst case, it’s O(N*M).

      • Thank you for making it clear for me, as I have some issues with estimating time complexity:)
        Though I am a bit confused, about assigning “new int[N]”, as I thought it does not iterate through all elements to allocate memory for each of them and assign separately:) I assumed that memory is allocated for the whole array. Please, check that.
        Sorry for my code, though judging by it, I would like to point out on one thing. Lets assume that we have a worst case scenario and all operations are max_counter, then operation “counters = new int[N];” will be performed only once, for the last element. That makes time complexity, according to your formula (which I did not know, really thank you for that), it will be O(N+M+N*1) => O(N+M);
        The real worst case scenario is when each update operation is followed by max_counter. In that case time complexity will be O(N+M+N*N/2), according to your formula again. That makes complexity O(N^2), not O(N*M). Although I do not think that it requires O(N) to allocate memory for an array, I might be wrong.
        I am not trying to prove that my solution is 100% perfect and works everywhere, I was just a bit confused by your judgement based on Codlity reply and your assumptions that it passes all tests by chance.

        • Yeah, you are right, it is O(N) for declaring array with N length. Thank you.
          That means in the worst case scenario my solution will be performed at O(N^2).

          • Yeah! Discussion is greatly helpful to all of us! To err is human.
            Enjoy Coding! And welcome to discussion on any solution here!!!
            PS: please add a few description words with your code next time. So that we could know what’s happening~ Thanks!

  2. Yes, thank you for the blog and solutions.
    I am still learning stuff, and this blog is very helpful.
    Yes, my mistake, I understand, should have added comments, as I forgot myself what is going on in my code:)

    • Comment does matter. It helps a lot when you are communicating with others. And it will help you a lot when you come back to read your own code after days.
      In addition to comments, a few sentences, about why you are posting your code here, are really appreciated.
      You are more than welcome! Enjoy coding!

    • Your solution is great! It provides us another idea to solve this challenge: replay the increase(X) values following the last maxCounter(). Thanks!!!
      FYI: you forgot to comment out one cout at line 10.
      PS: Thanks for visiting my blog! So happy to see it be helpful to others!

  3. Can you tell me why this solution failed the performance test? Thanks in advance!
    (https://codility.com/demo/results/demoV6MRWN-MY5/)

  4. PHP – O(N + M) – 100% / 80%
    https://codility.com/demo/results/demoKC2FYJ-JWD/

    Can’t get more performance with that way
    So I started to do it in the way that I am finding last max counter and then increase particular fields
    But I got some Correctness problems https://codility.com/c/run/demo7UZSUV-T8N
    Admin: your second solution is here: https://codility.com/demo/results/demo7UZSUV-T8N/

    • I cannot open the second URL. And in most cases, I cannot help you to debug.
      For your first solution, the performance issue is the line #10. Please use lazy write as shown in my post.

    • I found and read your second solution. I cannot understand it fully. But it definitely has some bugs. After you got a max_counter instruction, you may increase the value $result[$inc-1]++ without updating it to max_counter.
      Please ask question only after you read all the blog post and all the comments.

  5. C++ 100% solution.
    At the start a have a for loop to consolidate all numbers greater than N into one number. So if N = 5 and the vector like this { 7,8,9,1,2,3,4,7,7,8,9,5,6} this will be reduced to {1,2,3,4,7,5,6}. The reason I did the reduced vector was because I was maxing the counter in the forloop that incremented each counter!

    Admin: in the original post, Simon used a different function signature. I modified it so that, every reader could use it directly in Codility.com.

  6. I solved this in the C programming language. When I faced this test at the first time, what frustrated me was the structure declaration of the result, that is;

    I could easily notice that C is a pointer to a dynamic array (the counter), but L was not so clear. However, after a few trial and errors, I guessed that L is the length of the array. I’m not one hundred percent sure about this, but anyway I managed to get 100/100 score with the complexity of O(N + M). I think it would be better if Codility was a little more friendly, but we know that we can not blame them.
    The code I posted is somewhat broken. Here I will add the URL what I did;
    https://codility.com/demo/results/demoKZGHHC-KEP/

    • Yes, it is unclear in the question statement. I encourage you to contact them to fix it. The staff in codility.com is nice and helpful. 🙂

      • I e-mailed the staff in codility.com as suggested, and confirmed that C stands for the counter and L for the length. I also heard that they have a roadmap to fix this and make it more clear.
        Thanks again for your recommendation!

        • You got it! I had some similar issue and emailed them. Therefore I know it is nice communicating with codility.com 🙂
          Enjoy coding!

  7. Ruby 100%

  8. I slight variation on your solution using list comprehension. Took me a while to work out that I couldn’t use max() in the first loop to get the max_val without sacrificing performance. Still so much to learn!

  9. Hi there,
    I am still a little bit puzzled:
    The task is :
    ” … if A[K] = N + 1 then operation K is max counter…”
    Why do you write

    and not:

    Thanks in advance!

    • Because the problem says: “each element of array A is an integer within the range [1..N + 1].” If the condition “1 <= command <= N" failed, the command MUST be N + 1.

      • Totally fine! You were very close to the right formation. You began the code with a pre tag, but ended it with a “code” tag, which is wrong. You should use pre tag at both the beginning and the end. Or code tag in both places. Please read the “Guideline for Comments” on the right column of the blog for more information.
        Thanks for sharing!!!

  10. This is another Java solution with some comments as suggested earlier:

  11. C++ solution:

  12. This is my Python solution:

    Fails performance test for large data sets… Any idea ?

  13. There doesn’t seem to be a 100% python solution posted. Both of Sheng’s solutions fail the performance test, when they are submitted to Codility. I managed to get 100% solution by not overwriting the list every time the N+1 max value command is issued. Instead two numbers are remembered the current max value and the previous max value, at the time of the last N+1 max value assignment command. This avoids the O(N) list creation time. Each array value is updated after all the commands from list A are run.

    • Thanks for your comment! However, I do not know how did you get the conclusion “Both of Sheng’s solutions fail the performance test”.
      For the first solution, I explicitly said, it’s bad in the worst-case. For the second one, I tried again on Codility and it still passes the Codility test.
      Finally, please read the “Guideline for Comments” for posting code. I cannot see your complete solution. With your incomplete post, I did not see much difference between your solution and mine.

  14. this seems to work 100%.
    https://codility.com/demo/results/trainingQ8JXGP-4K3/

  15. How about this

  16. this is my solution, similar with yours i think, but with a little tweak, how ever i got only 80 in performance, not sure why, can not find any other boost.

    • Please read the article fully. The key point of the solution is “lazy-write”. “space = i == N+1 and [maxCounter]*N or space” will lead to 80% in performance testing. Thanks!

  17. Here is my Java solution, 100%

  18. Thank you! Before I found your solution, I submitted 2 Java solutions to this problem and I managed to get 77% and 66% overall on this problem due to failures in the performance tests. Finally, after reading your Python solution I realized that I had an inefficiency in the else statement (line 15-18 in your code) – I didn’t need to set all the variables in the array to that value every time, just keep track of the variable. My third solution finally got 100% success. Here it is:

  19. Ruby 100 / 100 – O(N + M)
    https://app.codility.com/demo/results/training5C528M-GM8/

  20. P.S. Sorry — there was similar solution by M A, I didn’t see it until I posted. Guess mine might be a tiny bit more concise though. I got to this solution by introducing last_op boolean flag, which almost got me there (100 / 60):
    https://app.codility.com/demo/results/trainingMNJ6SN-J83/

    Then I hit on the lazy writing, through seeing the expression spelled in English, and that got me to 100 / 100.

    As far as I now understand, the lazy writing the of the last_max will reduce complexity to O(N) in the increase(x) part, and checking whether the max_counters(x) op has been the last one, will cut the complexity in the max_counters part way below O(N**2) — the more max_counters, the more probability that they will come in a row, so nothing needs to be done with the counters.

    I’m still not entirely convinced that counters = [last_max] * n (populating an array with a given identical value) is necessarily O(N). Isn’t there any magic shortcut to splash a value across an array? Something like Array.new(max)? Implemented in Assembler by Dart Vader in 1066 using turbo hash tables 🙂

  21. C# 100% – O(N + M)
    https://app.codility.com/demo/results/trainingK6U2XK-DQY/

  22. Hello All, Its really fun in solving the codility problems. I could solve the problem but I am nt sure ahy my preformance is always not good. For the same problem, I tried

    A=[3,4,4,6,1,4,4]
    N=5
    solution(N,A)

    Can someone help me in understanding how to improve the performance of the code. Pretty new to Python. Learning by myself 🙁
    Looking for some valuable feedback and help in improving my performance!

    Thanks a lot in advance!

    https://app.codility.com/demo/results/trainingCR4RK3-4NQ/

    • Your else branch is the bottleneck of you performance. You can speed up by updating your counter_set, which is not a set btw, only once, outside of the for loop.

  23. Hi what about this?

  24. Go solution – O(N+M) complexity

    • This passes all tests. No timeout errors.

      Detected time complexity:
      O(N + M)
      expand allExample tests
      ▶example
      example test✔OK
      expand allCorrectness tests
      ▶extreme_small
      all max_counter operations✔OK
      ▶single
      only one counter✔OK
      ▶small_random1
      small random test, 6 max_counter operations✔OK
      ▶small_random2
      small random test, 10 max_counter operations✔OK
      expand allPerformance tests
      ▶medium_random1
      medium random test, 50 max_counter operations✔OK
      ▶medium_random2
      medium random test, 500 max_counter operations✔OK
      ▶large_random1
      large random test, 2120 max_counter operations✔OK
      ▶large_random2
      large random test, 10000 max_counter operations✔OK
      ▶extreme_large
      all max_counter operations✔OK

  25. Swift solution 100% – inspired by solutions above!

    https://app.codility.com/demo/results/trainingJ6VW2B-PN8/

  26. Here’s a O(N) JavaScript solution (unless I’m wrong, please correct me!) (To be more precise, I evaluate it to be O(2N+M), which is less than O(3N), which I understand evaluates to O(N) ?)
    You only need to keep track of how many new additions to specific numbers there are after the last reset. Then you fill an array with the value of the last reset and only add the missing additions.

     function solution(N, A) {
        // write your code in JavaScript (Node.js 8.9.4
        let current_max = 0;
        let last_max = 0;
        let additions = {};
        A.forEach(n => {
            if (n  current_max ? additions[n-1] + last_max : current_max
            }
            else if (n > N) {
                additions = {};
                last_max = current_max;
            }
        })
        const counters = Array(N).fill(last_max)
        Object.keys(additions).forEach(key => {
            counters[key] += additions[key]
        })
        return counters
    } 
    • Time Complexity – O(N+M). 100%. List comprehension in the last step instead of directly applying max() inspired from one of the other comments on Python. Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!