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

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.

• 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,

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 !