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

Question Name: Peaks

**UPDATE on July 18th 2015**: Many thanks to @Antonio Correia (https://34.145.67.234/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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | def solution(A): from math import sqrt A_len = len(A) peaks_until_here = [0]*A_len # Retrieve how many peaks exist from beginning to current # position. for index in range(1, A_len-1): peaks_until_here[index] = peaks_until_here[index-1] if A[index] > A[index-1] and A[index] > A[index+1]: peaks_until_here[index] += 1 if A_len < 3 or peaks_until_here[-2] == 0: # The array is too short to have a peak. OR # There is no peak in this array. return 0 peaks_until_here[-1] = peaks_until_here[-2] max_blocks = 0 # Compute every possible partition plan, and find out the # one with most blocks. for candidate in range(1, int(sqrt(A_len))+1, 1): if A_len % candidate == 0: blocks, block_size = candidate, A_len//candidate # Check the first block. if peaks_until_here[0] < peaks_until_here[block_size-1]: # Check the following blocks. for each_block in range(block_size, A_len, block_size): if peaks_until_here[each_block-1] == \ peaks_until_here[each_block+block_size-1]: # No peak is found in the next block # This partition plan is not accepted break else: max_blocks = blocks if candidate * candidate == A_len: # If candidate is equal to sqrt(A_len) exactly, # candidate would equal to A_len//candidate. continue block_size, blocks = candidate, A_len//candidate # Check the first block. if peaks_until_here[0] < peaks_until_here[block_size-1]: # Check the following blocks. for each_block in range(block_size, A_len, block_size): if peaks_until_here[each_block-1] == \ peaks_until_here[each_block+block_size-1]: # No peak is found in the next block # This partition plan is not accepted break else: return blocks return max_blocks |

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

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.

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

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

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.

Thanks for your novel solution!

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

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.

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.

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

Hello,

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

Thanks a lot for sharing.

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

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.

You are absolutely right! Many thanks!!!

I am fixing the bug.

Here’s my solution.

Great! Thanks for sharing!

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

Expected answer is 3

I tried. And it returns 3.

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!

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

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

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?

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!

Sorry, I did not know also~

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

my submission, simple, 85% correct, can be improved, not focussing on it now, need to practice other algos

C++ solution 100/100

For input [1, 2, 1] * 10 (i.e. 30 numbers, 10 peaks) your solution returns 30 (I think the correct answer is 10). Unless I’m missing something, you cannot have 30 peaks in an array of length 30.

Your test case: [1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1]

Returned value: 10

You might mis-read my code 🙂

C# solution 100%

Hi Sheng, can you please clarify something for me? I don’t understand how your solution verifies the constraints of the problem correctly.

If the distance between any two flags must be GREATER THAN OR EQUAL TO the total number of flags placed, I don’t see how simply checking whether a two peaks exist in two consecutive “blocks” of a given length can sufficiently prove that. What if the peak in the ith block is at the right-most end and the peak in the i+1th block is at the left-most end? They could be separated by a minimum of 2 elements…

For example, take the following array:

[1, 2, 1, 2, 1, 1, 2, 1, 1]

There are 9 elements and 3 peaks. According to your solution, if I divided the array into 3 blocks of size 3, then the max amount of flags I could place would be 3 since there is 1 peak in each of the 3 blocks.

But if you look at the 1st and 2nd peak, they exist at indices 1 and 3 which is a distance of |3-1| = 2 …. they are not separated by enough distance if we wanted to place 3 flags.

Sure enough, your code does return 3 for this array. What am I missing here? Am I misinterpreting something? Thanks

I just double-read the question description on Codiity. And I did not see any requirement about “the distance between any two flags must be GREATER THAN OR EQUAL TO the total number of flags placed”.

Hi,

I’m very new to coding, but I’ve found slightly different solution which obtained perfect score, wanted to share it.

Thanks for sharing and enjoy coding!

Hi,

I got 100% with this solution in Java. I did one thing for the first loop to find peaks, i.e. after finding the peak I am skipping the next element as it is less than the peak.

I know this solution can be further optimized by group members but this is the best I can do as of now, so please let me know how can I optimize this more.

Detected time complexity: O(N)

https://app.codility.com/demo/results/trainingG35UCA-7B4/