Extract Local Maxima [duplicate]

Given an array of positive integers, output an array of all the elements that are greater than or equal to the adjacent ones. Most elements will have two adjacent elements; the first and last element are special cases, as they only have one adjacent element.

You may assume that the array contains at least two elements.

Test cases:

Input               | Output
[4,2,6,12,4,5,4,3]  | [4,12,5]
[1,2]               | [2]
[1,2,3,2,1]         | [3]
[3,2,1,2,3]         | [3,3]
[4,4]               | [4,4]
[2,4,4,4,1]         | [4,4,4]
[2,3,3,4]           | [3,4]
[4,3,3,4]           | [4,4]


This is , shortest code wins!

• @PeterTaylor I think what's meant is "For the first or last element to be included in the output, ..."
– xnor
Commented Jul 14, 2017 at 18:50
• @PeterTaylor xnor is correct. Commented Jul 14, 2017 at 18:52
• Related Commented Jul 14, 2017 at 18:56
• Also related: Finding Local Extremes Commented Jul 15, 2017 at 7:34
• I've voted to close this as a duplicate of Finding Local Extremes as this is a subset of that challenge Commented Dec 26, 2020 at 23:27

Python, 54 bytes

f=lambda l,*p:l and l[:p<=l[:1]>=l[1:2]]+f(l[1:],l[0])


Try it online!

I/O is with tuples rather than lists.

Python, 57 bytes

f=lambda l,p=0:l and l[:[p]<=l[:1]>=l[1:2]]+f(l[1:],l[0])


Try it online!

Alt 57:

f=lambda l,p=0:l and l[l<[max(p,*l[:2])]:1]+f(l[1:],l[0])


Mathematica 22 Bytes

Pick[#,MaxDetect@#,1]&

• Incidentally, this would also work on higher dimension arrays. Commented Jul 14, 2017 at 18:51

f l=[j|i:j:k:_<-scanr(:)[0]$0:l,k<=j,i<=j]  Try it online! scanr(:)[0] makes a list of the tails of (0:l), each with a final 0, e.g. for l = [4,3,3,4]: [[0,4,3,3,4,0],[4,3,3,4,0],[3,3,4,0],[3,4,0],[4,0],[0]] which is pattern matched agains i:j:k:_ to extract all lists with at least 3 elements which are named i, j, and k. Keep j if its >= i and j. Edit: Ørjan Johansen saved 7 bytes. Thanks! • i:j:k:_<-scanr(:)[0]$0:l is shorter. (Slightly adjusting the "standard" tails=scanr(:)[] trick.) Commented Jul 14, 2017 at 23:55
• @ØrjanJohansen: oh, I've used that trick before myself, but somehow missed it here. Thanks a lot!
– nimi
Commented Jul 15, 2017 at 9:52

Jelly,  13 12  11 bytes

0;;0»3\f"⁸Ẏ


A monadic link taking a list of positive integers and returning the filtered list containing only those which are greater than or equal to all their neighbours.

Try it online!

Previous 12 byter:

0;INżI>0ḄNMị


Previous 13 byter:

0;;0ṡ3M€ċ€2Tị


How?

0;;0»3\f"⁸Ẏ - Link: list of positive integers, A
0;          - a zero concatenated with A
;0        - concatenate a zero
3\     - 3-wise reduce with:
»       -   maximum (yields a list of the maximums in each overlapping window of 3)
⁸  - chain's left argument, A
"   - zip with:
f    -   filter keep (i.e. keep the maximal if it is [in] the [length 1 list
-                     of the] respective original element)
Ẏ - flatten by one level

• Well I think there may be a way to use 3-wise reduction but I have not worked it out. Commented Jul 14, 2017 at 20:03
• I was right - a 3-wise reduce with the maximum dyad, » - how about 10 though..? Commented Jul 14, 2017 at 22:04
• 10 bytes. Also 10 bytes Commented Dec 26, 2020 at 23:01
• @cairdcoinheringaahing indeed, I don't think either of those were possible at the time. Commented Dec 27, 2020 at 0:30

Dyalog APL, 31302822 21bytes

{⍵/⍨(⌈/=2⌷⊢)¨3,/∊0⍵0}


Try it online!

Explanation (I'm not good at explaining things):

0⍵0       - [0,input,0]   (it looks like a face!)
∊         - flatten
3,/       - split into overlapping sections of length 3.
(⌈/=2⌷⊢)¨ - Whether the middle element is the maximum (applied to every section)
⍵/⍨       - index


p%(h:t)=[h|h>=p,[h+1]>t]++h%t
_%e=e
(0%)


Try it online!

JavaScript (ES6), 40 bytes

a=>a.filter((e,i)=>!(e<a[i-1]|e<a[i+1]))


Python 3, 84 75* 71 bytes

lambda l,k=[0]:[j for x,j in enumerate(l)if(k+l+k)[x+2]<=j>=(k+l+k)[x]]


Try it online!

*@LeakyNun saved 9 bytes using a clever operator trick.

• lambda l,k=[0]:[l[i]for i in range(len(l))if(k+l+k)[i+2]<=l[i]>=(k+l+k)[i]] Commented Jul 14, 2017 at 18:52

Jelly, 15 bytes

2ị⁼Ṁ
0;;0ṡ3Ç€Tị


Try it online!

05AB1E, 15 14  13 bytes

ü‹0¸«sĆÁü›+_Ï


Try it online!

Explanation

ü‹             # pairwise comparison for less than
0¸«          # append 0
s         # swap input to top of stack
Ć        # enclose, append the head of the list
Á       # rotate right
ü›     # pairwise comparison for greater than
+    # add the two boolean lists
_   # logical negate
Ï  # keep only elements of input that are true in the resulting list


Previous 15 byte solution

¬s¤)˜Œ3ùεZQ1è}Ï


Try it online!

Explanation

¬                # get head of input
s¤              # get tail of input
)˜            # wrap stack in flattened list
# produces the input list with the first and last element duplicated
Œ3ù         # push sublists of length 3
ε        # apply transformation on each triple
ZQ      # ... check each element for equality to the max
1è     # ... get the middle element
}    # end transform
Ï   # keep only elements of input that are true in the resulting list


R, 44 bytes

pryr::f(x[(x>=c(0,x)&x>=x[-1])[1:sum(x|1)]])


which evaluates to the function:

function (x)
x[(x >= c(0, x) & x >= x[-1])[1:sum(x | 1)]]


Compares x to c(0,x), so with x shifted one position to the right. Also compares x to x[-1], so one position shifted to the left. These both are TRUE if there is a maximum there. & to take the AND of these booleans. Because of the wrapping nature of R's vectors when they are not the same length, we have to truncate the result at the length of x, which is found by taking sum(x|1). We then plug in the boolean vector, taking only the true indices of x and return that.

Note, because these logical operations are done with unequal length vectors, R will complain. A lot. But the correct output will be there amidst the warnings:

> pryr::f(x[(x>=c(0,x)&x>=x[-1])[1:sum(x|1)]])(c(4,2,6,12,4,5,4,3))
[1]  4 12  5
Warning messages:
1: In x >= c(0, x) :
longer object length is not a multiple of shorter object length
2: In x >= x[-1] :
longer object length is not a multiple of shorter object length
3: In x >= c(0, x) & x >= x[-1] :
longer object length is not a multiple of shorter object length


R, 42 bytes

function(x)x[c(d<-diff(x),0)<=0&c(0,d)>=0]


Try it online!

2 bytes shorter than JAD's solution. diff computes successive differences; then keep only the entries greater than both neighbours.

Pyth, 20 bytes

-.b*YqYeSN.:++0Q03Q0


To be golfed...

Test suite.

R, 68 bytes

function(a)a[a==sapply(1:length(a),function(i)max(c(0,a,0)[i+0:2]))]


Try it online!

• pryr::f(expression) is a shorter way to declare a function than function(a)expression.
Commented Jul 15, 2017 at 10:28
• Also, sum(a|1) is a shortcut for length(a).
Commented Jul 15, 2017 at 10:50
• See my solution for a shorter approach.
Commented Jul 15, 2017 at 11:05

for(;$g=$argv[+$i];$l=$g)$g<$l|$g<$argv[++$i]?:$r[]=$g;print_r($r);  Try it online! Retina, 51 bytes \d+$*
^

M!(?<=(^|1+) )(\1\d*)\b(?! 1\2)
^¶

%1


Try it online

q, 39 bytes

{x where x = -1 _ next 3 mmax x,last x}

• I've never heard of this language before. Do you know anywhere I can try or download it? Commented Jun 6, 2019 at 2:41
• Sure, kx.com, docs: code.kx.com Commented Jun 6, 2019 at 7:03

Stax, 10 bytes

úâH◄(☼bM•Å


Run and debug it

It produces output as newline separated values on standard output.

Unpacked, ungolfed, and commented, it looks like this.

f       filter each value in input using the rest of the program; implicitly printing kept values
x0|S  input pre- and post-pended with zero
3B    split into batches of 3
i@    get the i-th batch, where i is the iteration index
|M=   is the current value equal to the max from the batch?


Run this one

Updated: Just found a 9-byte solution. Will update explanation later:

Stax, 9 bytes

▀▓ûa¥╓╧↨⌐


Run and debug it

Perl 5-a, 37 bytes

map{$_>=$F[++$i]&$_>=$p&&say;$p=\$_}@F


Try it online!