## Peaks

### February 15, 2019

Given an array of integers, a peak is a subarray of minimal length in which the integer values increase and then decrease. For instance, in the array [5,5,4,5,4] there is a peak [4,5,4] and in the array [6,5,4,4,4,4,4,5,6,7,7,7,7,7,6] there is a peak [6,7,7,7,7,7,6]. Note that [4,5,6,7,7,7,7,7,6] shows a pattern of increasing and decreasing values, but it is not minimal because the first two items can be removed and the remaining subarray remains a peak. The array [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8] has two peaks, [4,5,4] and [8,9,9,8].

Your task is to write a program that finds all of the peaks in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 10 Responses to “Peaks”

1. matthew said

Looks like a job for Regular Expressions:

```import re
def compare(x,y): return '<' if x < y else '=' if x == y else '>'
def findpeaks(a):
cmpstring = "".join([compare(a[i],a[i+1]) for i in range(len(a)-1)])
return (match.span() for match in re.finditer('<=*>',cmpstring))

a = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]
for (start,end) in findpeaks(a):
print(a[start:end+1])
```
```[4, 5, 4]
[8, 9, 9, 8]
```

By the way, what’s with the “This post is ad-supported” in the emails? Didn’t used to get them, they are quite annoying.

2. Smith said
```def peak(a=[5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]):
a = np.pad(np.array(a), (0, 1) , mode='edge')
indices = np.arange(len(a)-1)

# where first derivative is not zero, normalized to -1 and 1
d1 = a[:-1] - a[1:]

# where first derivate changes from negative 1 to positive 1

return [a[f:s+1].tolist() for f,s in zip(l,r)]

peak()
```
```[[4, 5, 4], [8, 9, 9, 8]]
```
3. Globules said

A Haskell version. We run-length encode the input lists so that we only have to look for three consecutive values that match the pattern low-high-low.

```import Control.Arrow ((&&&))
import Data.List (group)

type Run a = (Int, a)

-- Run length encode the argument.
rle :: Eq a => [a] -> [Run a]
rle = map (length &&& head) . group

-- Run length decode the argument.
rld :: [Run a] -> [a]
rld = concatMap (uncurry replicate)

-- Expand three runs into a list.
expand :: (Run a, Run a, Run a) -> [a]
expand (x, y, z) = rld [x] ++ rld [y] ++ rld [z]

-- Trim the leading and trailing runs to a single element each.
trim :: (Run a, Run a, Run a) -> (Run a, Run a, Run a)
trim ((_, x), keep, (_, z)) = ((1, x), keep, (1, z))

-- Do these three runs indicate a peak?
isPeak :: Ord a => (Run a, Run a, Run a) -> Bool
isPeak ((_, x), (_, y), (_, z)) = x < y && y > z

-- The list of peaks in the argument list.
peaks :: Ord a => [a] -> [[a]]
peaks = map (expand . trim) . filter isPeak . consec . rle
where consec xs = zip3 xs (drop 1 xs) (drop 2 xs)

main :: IO ()
main = do
print \$ peaks ([] :: [()])
print \$ peaks 
print \$ peaks [1, 2]
print \$ peaks [5, 5, 4, 5, 4]
print \$ peaks [6, 5, 4, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 6]
print \$ peaks [5, 5, 5, 5, 4, 5, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 9, 8]
```
```\$ ./peaks
[]
[]
[]
[[4,5,4]]
[[6,7,7,7,7,7,6]]
[[4,5,4],[8,9,9,8]]
```
4. matthew said

Here’s another Haskell solution. It uses a regex like my first solution, but since we don’t have regexs for arbitrary data types (don’t see why not), I’ve implemented simple regex matching as well:

```data Pattern a = A a | Seq [Pattern a] | Alt (Pattern a) (Pattern a)

-- A simple regex matcher. Try to match initial segment of
-- list. Return list of (length, remaining list) pairs.
match :: Ord a => Pattern a -> (Int,[a]) -> [(Int,[a])]
match (A a) (n,[]) = []
match (A a) (n, a':s)
| a == a' = [(n+1,s)]
| otherwise = []
match (Seq []) ns = [ns]
match (Seq (p:pp)) ns = concatMap (match (Seq pp)) (match p ns)
match (Alt p1 p2) ns = match p1 ns ++ match p2 ns

-- Find all matches and return list of (start,end) pairs
matchall p n [] = matchone p n []
matchall p n s = matchone p n s ++ matchall p (n+1) (tail s)
matchone p n s = [(n,n') | (n',s') <- match p (n,s)]

-- Define star as a recursive pattern
star p = p' where p' = Alt (Seq []) (Seq [p,p'])

re = Seq([A GT,star(A EQ),A LT])

prepeaks a = matchall re 0 (zipWith compare (tail a) a)
peaks a = [take (n-m+1) (drop m a) | (m,n) <- prepeaks a]

main = do
print \$ peaks 
print \$ peaks [1, 2]
print \$ peaks [5, 5, 4, 5, 4]
print \$ peaks [1, 2, 1, 2, 1, 2, 1]
print \$ peaks [6, 5, 4, 4, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7, 6]
print \$ peaks [5, 5, 5, 5, 4, 5, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 9, 8]
```
5. Daniel said

Here’s a solution in C.

```#include <stdio.h>
#include <stdlib.h>

typedef struct peak {
int idx;
int len;
} peak_t;

void get_peaks(int* array, int n, peak_t** peaks, int* n_peaks) {
int capacity = 1;
*peaks = malloc(sizeof(peak_t) * capacity);
*n_peaks = 0;
peak_t peak;
int in_peak = 0;
for (int i = 1; i < n; ++i) {
if (array[i] > array[i - 1]) {
peak.idx = i - 1;
peak.len = 2;
in_peak = 1;
continue;
}
if (!in_peak) continue;
++(peak.len);
if (array[i] == array[i - 1]) continue;
++(*n_peaks);
if (*n_peaks > capacity) {
capacity *= 2;
*peaks = realloc(*peaks, sizeof(peak_t) * capacity);
}
(*peaks)[*n_peaks - 1] = peak;
in_peak = 0;
}
}

void free_peaks(peak_t** peaks) {
free(*peaks);
*peaks = NULL;
}

void print_array(int* array, int n) {
printf("[");
for (int i = 0; i < n; ++i) {
if (i > 0) printf(", ");
printf("%d", array[i]);
}
printf("]\n");
}

int main(int argc, char* argv[]) {
int n = argc - 1;
int* array = malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i+1]);
}
peak_t* peaks;
int n_peaks;
get_peaks(array, n, &peaks, &n_peaks);
for (int i = 0; i < n_peaks; ++i) {
print_array(array + peaks[i].idx, peaks[i].len);
}
free_peaks(&peaks);
free(array);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out 5 5 5 5 4 5 4 5 6 7 8 8 8 8 8 9 9 8
[4, 5, 4]
[8, 9, 9, 8]
```
6. Daniel said

Here’s a solution in Python.

```def get_peaks(l):
tmp = [y - x for x, y in zip(l, l[1:])]
tmp = [x for x in enumerate(tmp) if x != 0]
tmp = [(x, y) for x, y in zip(tmp, tmp[1:]) if x > 0 > y]
tmp = [l[x:y+2] for x, y in tmp]
return tmp

l = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]
for peak in get_peaks(l):
print(peak)
```

Output:

```[4, 5, 4]
[8, 9, 9, 8]
```
7. matthew said

Here’s a slightly improved version of that regex matcher:

```data Pattern a = A a | Seq [Pattern a] | Alt [Pattern a]

match :: Eq a => Pattern a -> (Int,[a]) -> [(Int,[a])]
match (A a) (n,[]) = []
match (A a) (n, a':s)
| a == a' = [(n+1,s)]
| otherwise = []
match (Seq pp) ns = foldl (flip (concatMap . match)) [ns] pp
match (Alt pp) ns = concatMap (flip match ns) pp
```
8. Daniel said

Here’s another Python solution.

```import numpy as np

def get_peaks(l):
x = np.sign(np.diff(l))
y = np.nonzero(x)
x = np.diff(x[y])
x = np.where(x == -2)
x = [l[y[x]:y[x+1]+2] for x in x]
return x

l = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]

for peak in get_peaks(l):
print(peak)
```

Output:

```[4, 5, 4]
[8, 9, 9, 8]
```
9. Daniel said

In line 8 of my last post, I used the same name for both the list and the variable used to loop over the list. It seems to work, but was not my intent, arising from a renaming of variables.

Here’s the updated line 8.

```x = [l[y[z]:y[z+1]+2] for z in x]
```
10. Smith said