Codility ‘Peaks’ Solution

Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. A peak is an array element which is larger than its neighbors.

Link

Peaks

Complexity:

expected worst-case time complexity is O(N*log(log(N)));

expected worst-case space complexity is O(N)

Execution:

I first compute all peaks. Because each block must contain a peak I start from the end and try to find a integral divisor sized block. If each block contains a peak I return the size.

Solution:

def solution(A):
    peaks = []

    for idx in xrange(1, len(A)-1):
        if A[idx-1] < A[idx] > A[idx+1]:
            peaks.append(idx)

    if len(peaks) == 0:
        return 0

    for size in xrange(len(peaks), 0, -1):
        if len(A) % size == 0:
            block_size = len(A) // size
            found = [False] * size
            found_cnt = 0
            for peak in peaks:
                block_nr = peak//block_size
                if found[block_nr] == False:
                    found[block_nr] = True
                    found_cnt += 1

            if found_cnt == size:
                return size

    return 0


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Mikhail Manukhin

    Martin,
    There is a slight improvement which is possible in your code – we can use a simple integer variable instead of boolean array. It will store the index of the last block where peak is seen. It is possible because peaks are in sorted order.

  • Tom K

    Hi Martin,

    Thanks for your solution.

    I’m confused with the check at line 12. Any array size that is a prime number would return a max of one flag.
    For instance with the given array [1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 2] and from my understanding, there should be a maximum of 3 flags that can be set. Your solution would return 1.

    Cheers

    • Hi Tom,

      the task specifies that each block (containing a flag or not) has to be of equal size. Your array is of a prime size (11), therefore there can only be 1 or 11 blocks of peaks.

      You are right, in your array there are 3 peaks, but only 1 block of integral size (11) with a peak in it.

      With an array of size 12, there could be 2,3,4 or 6 such blocks.

      I could replace lines 11 and 12. It is not necessary to generate all numbers for len(peaks) to 1. I could start at the closest size multiple smaller than len(peaks) and decrement by size. But it did not seem necessary.

      -Martin

      • Tom K

        Thanks Martin. I switch between peaks and flags exercises !