# Solution to Max-Counters by codility

19 Jan

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

### 62 Replies to “Solution to Max-Counters by codility”

1. the.sentinel.au says:

java, 100%

• Sheng says:

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

• wujek says:

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?

• Sheng says:

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

• Sheng says:

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

2. the.sentinel.au says:

Hmmm.. Could you explain why your solution is O(N+M) then and mine is not?

• Sheng says:

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

• the.sentinel.au says:

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.

• the.sentinel.au says:

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

• Sheng says:

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!

3. the.sentinel.au says:

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

• Sheng says:

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.
You are more than welcome! Enjoy coding!

4. I did not really bother about Donald Knuth’s statement “Premature optimization is the root of all evil” until I tried out codility. I managed to get it 100% correct and 60% perf. on the first try, but getting it to 100% perf. meant breaking the correctness.
C++, 100%
https://codility.com/demo/results/demoPHDVVG-UFJ/
Btw, this is a great website.

• Sheng says:

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!

5. JG says:

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

• Sheng says:

Please refer to my post. It explains everything about the right solution.

6. romanj says:

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

• Sheng says:

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.

• Sheng says:

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.

7. Simon says:

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.

8. Kim says:

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/

• Sheng says:

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. 🙂

• Kim says:

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.

• Sheng says:

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

9. a131a says:

Ruby 100%

10. Martin says:

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!

• Sheng says:

11. Klaus says:

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

and not:

• Sheng says:

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.

12. Edgar says:

• Edgar says:

JavaScript, 100%… I’m so sorry, I don’t know that use to crayon highlight syntax.

• Sheng says:

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!!!

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

14. df611 says:

C++ solution:

15. Richard Rajah says:

16. Mariusz says:

This is my Python solution:

Fails performance test for large data sets… Any idea ?

• Sheng says:

17. Sam says:

Wow, your python solution is brilliant!

18. Aseem says:

Hey!
I tried a solution similar to your first one, tried to improve performance using a frequency map instead. Somehow it fails even the correctness tests. This was a first attempt so I don’t bother about performance that much. Can you help me see where is the failure in this?
https://codility.com/demo/results/training739NPC-XNZ/

• Sheng says:

I did not see any reason to use FreqTable.

19. Scott says:

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.

• Sheng says:

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.

20. M A says:

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

• Sheng says:

Without lazy-write, I am a little afraid of its performance.

22. ach says:

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.

• Sheng says:

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!

23. Tomislav says:

Here is my Java solution, 100%

24. 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:

• Sheng says:

Great to see my blog is helpful! Enjoy coding 🙂

25. Nien says:

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

26. Nien says:

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 🙂

27. droid says:

28. kufre okon says:

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

29. Kylasam NA says:

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!

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

• Jack says:

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.

30. pabhio@o2.pl says:

31. Saakshi Malhotra says:

Go solution – O(N+M) complexity

• Saakshi Malhotra says:

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

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

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

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;
A.forEach(n => {
if (n  current_max ? additions[n-1] + last_max : current_max
}
else if (n > N) {
last_max = current_max;
}
})
const counters = Array(N).fill(last_max)