# Solution to Peaks by codility

26 Jan

Question Name: Peaks

UPDATE on July 18th 2015: Many thanks to @Antonio Correia (https://codesays.com/2014/solution-to-peaks-by-codility/#comment-11725) !!! @Antonio Correia found a huge bug in my solution, even though it passed the codility.com. The bug has been fixed.

### 24 Replies to “Solution to Peaks by codility”

1. Max says:

Hi Sheng, I’ve found a Java solution to this problem here http://rafal.io/posts/codility-peaks.html
but I like yours better, you loop until sqrt(lenA) and while storing the index of the peak like it’s done in that solution is interesting, I still prefer your method of memorizing the peaks_until_here[] and checking that number against next block’s number.
But I quite honestly did not understand your solution completely. It might be because I started learning Python on my own just last month, but starting from
blocks, block_size = candidate, A_len//candidate
I have some difficulties to fully grasp what you are doing there (starting from the meaning of the pasted code line, what does it do exactly? I have a hypothesis, but…), could you help me out?

thank you

• Sheng says:

It is trying and computing every possible partition plan. For a game with length 10, we could divide it into 2 blocks with 5 elements in each, or into 5 blocks with 2 elements in each. That is why we use two tries on each one candidate:
blocks, block_size = candidate, A_len//candidate
block_size, blocks = candidate, A_len//candidate

In terms of how to check whether the partition plan is acceptable or not, you could draw it on paper, and follow each step to simulate the program. That will help you to better understand it.

• Pedro Borges says:

Great solution, I went linear from 3 to length / 2 inclusive and while that may be faster for small cases and still conforms to O(N*log(log N)) your’s sound better. Perhaps, since we are looking for the smallest blockSize, perhaps I’d go further, placing the complements of block size in a list in reverse order and checking them in a new for loop. This way you ensure you parse them by order and don’t need the candidate variable, you can simply return immediately when found. This way you don’t need to parse ALL possible solutions, only until a match is found.

Cheers

• Sheng says:

Thanks! It is one of the key points of the solution that we need to narrow down the candidate range.

2. Martin says:

Hey, an alternative python solution.

I first count the number of peaks, and down from there I try to check if there is a peak in a block. Block sizes obviously must be integral peak_cnt divisors.

• Sheng says:

PS: I have no idea about the commment system of WP. But it is really unfriendly for code, possibly for security issue.

• Pa says:

Thank you Martin and Sheng! Two kind of related questions:

Can anyone please tell what is the time complexity of Martin’s code?

What would be the maximum number of peaks that an array of size n can have?

Thanks a lot for your help.

• stromek says:

Why is this solution O(n*log(logn))?

In my view, it iterates at most N times (or that many times how many divisors N have) over an array of peaks which can be in the worst case n/2 (every other item is peak). So in math it comes to O(n*n/3) = O(n^2). Unless we can say that number of divisors of N are at most log(logn) which I have never seen.

• Sheng says:

Yes, it is not. However, the “for size in xrange(len(peaks), 0, -1)” could be optimized with binary search to make it O(N*log(N)).

3. Mariusz says:

Hello,

Great site Sheng! Here is my C++ solution. Probably could be optimized a lot, but now I’m focusing on next task ðŸ˜‰

• Sheng says:

Thanks a lot for sharing.

I am sorry for the code post issue. I am trying to figure out why~

4. Antonio Correia says:

I am having 3 has result for A = [1,2,3,4,5,6,5,5,5,6,5,6] but the first slice does not have any peak.
The way you’re looking for peaks in the slices does not check if there is one peak on the first slice, but I may be wrong and missing something. Cheers.

• Sheng says:

You are absolutely right! Many thanks!!!

I am fixing the bug.

5. Ishaq says:

Here’s my solution.

• Sheng says:

Great! Thanks for sharing!

• Moschops says:

Gives answer as 1 for the codility test case {1,2,3,4,3,4,1,2,3,4,6,2}

• Sheng says:

I tried. And it returns 3.

6. micropentium6 says:

My original solution that passed all test cases is almost 60 lines! Then after checking your and all other people’s brilliant solutions, Martin’s is the closest one to mine. I managed to replace the bool array with a variable that marks the result for the division operation against the last peak. It’s trivial though.
My code is still around 50 lines, partially because of the curly bracket… ðŸ™‚

Could you please help me understand why my solution is NO(log(logN))? I know it’s definitely not O(N^2), but have trouble to round it down.

Thanks!

• Sheng says:

Sorry, I cannot figure it out~ It seems “for (int k : peaks)” works for O(N) and “if (0 == len % d)” limits the outside while to be O(logN) or O(log(logN)).

• micropentium6 says:

Thank you for the reply! After reading your solution by keeping peaks position up front, I came out this

7. psychic says:

Why is Sheng’s solution O(N*log(logN))??
It looks to me as if it’s O(sqrt(N)*N),

Because the outer look goes over sqrt(N) possible partition options, (even though not everything is divisible but I don’t know of a tighter bound)
for each possible partition, you might check a number of partitions that is O(N).
For example for an even number, when you check the partitions of size 2, you check N/2 paritions.
And that’s why it seems to me that it’s O(sqrt(N)*N), which is worse than (log(logN))*N).

I realize I’m wrong somewhere, but can’t see where. Can anyone explain to me please?

8. psychic says:

Could anyone explain to me why Sheng’s solution is O(N*log(logN)) and not O(N*sqrt(N)) ??
It seems to me that per each possible division up to sqrt(N), it goes all over all partitions.
But some paritions could have up to O(N) blocks, so isn’t this O(sqrt(N)*N))??

Thanks!

• Sheng says:

Sorry, I did not know also~

9. Boshu says:

Here is my solution in Python. 100/100. I used prefix sum.