Solution to Peaks by codility

26 Jan

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.

34 Replies to “Solution to Peaks by codility

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

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

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

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

  5. Here’s my solution.

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

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

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

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

  11. C++ solution 100/100

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

  13. C# solution 100%

  14. 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”.

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

  16. 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/

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!