# Finding Local Extremes

Write a function or program that takes in a list and produces a list of the local extremes.

In a list `[x_0, x_1, x_2...]` a local extreme is an `x_i` such that `x_(i-1) < x_i` and `x_(i+1) < x_i` or `x_(i-1) > x_i` and `x_(i+1) > x_i`. Notice that the first and last elements of the list can never be local extremes.

So for some examples

``````local_extremes([1, 2, 1]) = [2]
local_extremes([0, 1, 0, 1, 0]) = [1, 0, 1]
local_extremems([]) = []
``````

This is code golf so the shortest code wins!

-
To make sure I understand correctly: Numbers greater than the numbers on either side? – undergroundmonorail Feb 26 '14 at 21:57
@undergroundmonorail Greater or less than. So it either has to be a local minimum, where it's neighbors are both greater, or a maximum where they're both smaller – jozefg Feb 26 '14 at 21:57
Oh, I see. I misread it – undergroundmonorail Feb 26 '14 at 21:58
and what about sequence `1 2 2 1` shouldn't those `2` be considered as extremes too? - I know, this would make the solution much more difficult... – V-X Feb 27 '14 at 13:08

# Mathematica 66 58 51

## Current Solution

Shortened thanks to a contribution by Calle.

``````Cases[Partition[#,3,1],{a_,b_,c_}/;(a-b) (b-c)<0⧴b]&
``````

`Partition[#,3,1]` finds the triples.

`(a-b) (b-c)<0` is true if and only if `b` is below `a`, `c`, or above `a`,`c`. and looks at takes the signs of the differences. A local extreme will return either `{-1,1}` or `{1,-1}`.

Examples

``````Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{1, 2, 1}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{0, 1, 0, 1, 0}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{}]
Cases[Partition[#, 3, 1], {a_, b_, c_} /; (a - b) (b - c) < 0 :> b] &[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]
``````

{2}
{1, 0, 1}
{}
{10, 6, 9, 0, 1}

## Earlier Solution

This looks examples all triples (generated by `Partition`) and determines whether the middle element is less than both extremes or greater than the extremes.

``````Cases[Partition[#,3,1],{a_,b_,c_}/;(b<a∧b<c)∨(b>a∧b>c)⧴b]& ;
``````

## First Solution

This finds the triples, and looks at takes the signs of the differences. A local extreme will return either `{-1,1}` or `{1,-1}`.

``````Cases[Partition[#,3,1],x_/;Sort@Sign@Differences@x=={-1,1}⧴x[[2]]]&
``````

Example

``````Cases[Partition[#,3,1],x_/;Sort@Sign@Differences@x=={-1,1}:>x[[2]]]&[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]
``````

{10, 6, 9, 0, 1}

Analysis:

``````Partition[{9, 10, 7, 6, 9, 0, 3, 3, 1, 10}]
``````

{{9, 10, 7}, {10, 7, 6}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {0, 3, 3}, {3, 3, 1}, {3, 1, 10}}

`%` refers to the result from the respective preceding line.

``````Differences/@ %
``````

{{1, -3}, {-3, -1}, {-1, 3}, {3, -9}, {-9, 3}, {3, 0}, {0, -2}, {-2, 9}}

`Sort@Sign@Differences@x=={-1,1}` identifies the triples from {{9, 10, 7}, {10, 7, 6}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {0, 3, 3}, {3, 3, 1}, {3, 1, 10}} such that the sign (-, 0, +) of the differences consists of a `-1` and a `1`. In the present case those are:

{{9, 10, 7}, {7, 6, 9}, {6, 9, 0}, {9, 0, 3}, {3, 1, 10}}

For each of these cases, x, `x[[2]]` refers to the second term. Those will be all of the local maxima and minima.

{10, 6, 9, 0, 1}

-
Your Mathematica style is much more concise than mine. When do we start calling it "Wolfram Language"? – Michael Stern Feb 27 '14 at 1:20
I see this !Mathematica graphics – Dr. belisarius Feb 27 '14 at 1:24
Michael Stern, I suspect Wolfram Language will only become official at version 10, some form of which already available on Raspberry Pi. – DavidC Feb 27 '14 at 1:29
BTW, someone inserted a line of code that converts the Math ML to graphics. I'm not sure why. – DavidC Feb 27 '14 at 1:38
I'm not sure why he did it. I can't see any differences in the "modified" code – Dr. belisarius Feb 27 '14 at 2:09

# Javascript - 62 45 Characters

``````f=a=>a.filter((x,i)=>i&&i<a.length-1&&(a[i-1]-x)*(a[i+1]-x)>0)
``````

Edit

``````f=a=>a.filter((x,i)=>(a[i-1]-x)*(a[i+1]-x)>0)
``````
-

# J - 20 char

Couldn't help it ;)

``````(}.@}:#~0>2*/\2-/\])
``````

Explanation follows:

• `2-/\]` - Over each pair of elements in the argument (each 2-item long infix), take the difference.
• `2*/\` - Now over each pair of the new list, take the product.
• `0>` - Test whether each result is less than 0. This only happens if the multiplicands had alternating signs, i.e. it doesn't happen if they had the same sign or either was zero.
• `}.@}:` - Cut off the first and the last element, because those can't possibly be extrema, and we lost information for them anyway by doing the pairs stuff above.
• `#~` - Use the true values on the right side to pick items from the list on the left side.

Usage:

``````   (}.@}:#~0>2*/\2-/\]) 1 2 1
2
(}.@}:#~0>2*/\2-/\]) 0 1 0 1 0
1 0 1
(}.@}:#~0>2*/\2-/\]) i.0   NB. i.0 is the empty list (empty result also)

(}.@}:#~0>2*/\2-/\]) 3 4 4 4 2 5
2
``````
-
Umm, this may not work if the input is, say, 3, 4, 4, 4, 4, 5, i.e. you may get a zero in the "0=" step if 0 is added to 0. – Lord Soth Feb 27 '14 at 1:19
Also, I do not know about this language, but, instead of taking the signum in the first step, you can leave the difference as it is. Then, in the second step, multiply the elements instead, and in the third you may check if the product is negative (this also avoids that 0 problem). Perhaps this may result in a shorter code. – Lord Soth Feb 27 '14 at 1:21
Good catch, and yes, this saves two characters. Updating. – algorithmshark Feb 27 '14 at 1:50

# Ruby, 83706055 49 characters

``````f=->a{a.each_cons(3){|x,y,z|p y if(x-y)*(z-y)>0}}
``````

Prints all local extremes to STDOUT.

Uses the `<=>` "spaceship" operator, which I really like. (It returns 1 if the first thing is greater than the second, -1 if it's less, and 0 if equal. Therefore, if they add to -2 or 2, that means the middle is an extreme.)

Not anymore, as @daniero pointed out that the "obvious" way is actually shorter!

Changed yet again! Now it uses the awesome algorithm found in MT0's answer (+1 to him!).

Also, I like `each_cons` which selects each `n` groups of consecutive elements in an array. And trailing `if` is interesting too.

Overall, I just like how elegant it looks.

Some sample runs:

``````irb(main):044:0> f[[1,2,1]]
2
=> nil
irb(main):045:0> f[[1,0,1,0,1]]
0
1
0
=> nil
irb(main):046:0> f[[]]
=> nil
irb(main):047:0> f[[1,2,3,4,5,4,3,2,1]]
5
=> nil
irb(main):048:0> f[[1,1,1,1,1]]
=> nil
irb(main):049:0> f[[10,0,999,-45,3,4]]
0
999
-45
=> nil
``````
-
It's shorter to unpack x into 3 variables: `f=->a{a.each_cons(3){|x,y,z|p y if((x<=>y)+(z<=>y)).abs==2}}` – daniero Feb 27 '14 at 1:58
@daniero Thanks; I didn't even know you could do that! Edited – Doorknob Feb 27 '14 at 2:03
really? :D Btw, now that each term is 3 character shorter, it's overall cheaper to do `x>y&&y<z||x<y&&y>z` (even tho the spaceship operator is very pretty) ;) – daniero Feb 27 '14 at 2:20
also... `!((x..z)===y)` is even shorter though not as clever – Not that Charles Feb 27 '14 at 2:25
@Charles That fails when `x < z`. – Doorknob Feb 27 '14 at 2:31

# C++ - 208 chars

Longest solution again:

``````#include<iostream>
#include<deque>
using namespace std;
int main(){deque<int>v;int i;while(cin){cin>>i;v.push_back(i);}for(i=0;i<v.size()-2;)if(v[++i]>v[i-1]&v[i]>v[i+1]|v[i]<v[i-1]&v[i]<v[i+1])cout<<v[i]<<' ';}
``````

To use, enter your integers, then any character that will crash the input stream - any non-number characters should work.

Input: `0 1 0 x`

Output: `1`

-
You can use a `deque` instead of a `vector` to gain 2 characters. – Morwenn Feb 27 '14 at 10:01
Also, instead of using `i` and `j`, you can declare `int i;` right after the collection and use in is the two loops instead of declaring two variables. – Morwenn Feb 27 '14 at 10:02
Finally, you can probably get get rid of the increment `i++` in your for loop and begin your condition by `if(v[++i]>[i-1]...` in order to gain one character again. – Morwenn Feb 27 '14 at 10:04
@Morwenn Thanks. – Hosch250 Feb 27 '14 at 16:39

# Matlab - 45 bytes

``````x=input('');y=diff(x);x(find([0 y].*[y 0]<0))
``````
-

# Python 2.7 - 73 bytes

``````e=lambda l:[l[i]for i in range(1,len(l)-1)if(l[i]-l[i-1])*(l[i]-l[i+1])]
``````

Not too impressive (Look at every element of the list except the first and last, see if it's larger or smaller than its neighbours). I'm mostly only posting it because not everyone knows you can do `x<y>z` and have it work. I think that's kind of neat.

Yes, `x<y>z` is a cool feature of python, but it's not actually optimal in this case. Thanks to V-X for the multiplication trick, that didn't occur to me at all. Wrzlprmft reminded me that declaring an anonymous function is less keystrokes than `def x(y):`.

-
It’s shorter to use the `lambda` operator. – Wrzlprmft Feb 27 '14 at 10:06
`if(l[i]-l[i-1])*(l[i]-l[i+1])>0` would reduce the code by 11 characters... – V-X Feb 27 '14 at 13:25
@wrz Ah, you're right. I was thrown off by the fact that `def e(l):\n ` is the same number of characters as `e=lambda l:`, but I forgot that you don't need to use the `return` keyword. Thanks! – undergroundmonorail Feb 27 '14 at 13:53
@v-x Oh, I like that a lot. Thank you :) edit: Actually you can save more than that! Since `(l[i]-l[i-1])*(l[i]-l[i+1])` is `1` if `l[i]` is a local extreme and `0` otherwise, I don't need to use `>0`. I can just let python interpret it as a bool. :) – undergroundmonorail Feb 27 '14 at 13:53
@wrz I can't figure out how to edit a comment that's already been edited (the pencil icon seems to replace the edit button. is this by design?). I just wanted to add that, if I was smart, I'd have realized that my one-line function didn't need the `\n ` in the declaration at all! That would have saved two characters, but the inclusion of `return` still makes it not worth it. – undergroundmonorail Feb 27 '14 at 14:04

``````f a=[x|(p,x,n)<-zip3 a(tail a)(drop 2 a),x>p&&x>n]
``````
-
this only check local maximum, for minumum need to add || x<min p n – karakfa Feb 27 '14 at 19:46
`x>p&&x>n` has one less character than `x>max p n` :-) – yatima2975 Feb 27 '14 at 20:25
space after `,` is not necessary either. – karakfa Feb 27 '14 at 21:51
change `x>p&&x>n` to `(x>p)==(x>n)` for local minimums too, adds 4 more chars. – karakfa Jul 9 at 13:24

# Python with Numpy – 81 74 67 bytes (61 54 without the `import` line)

``````import numpy
e=lambda a:a[1:-1][(a[2:]-a[1:-1])*(a[1:-1]-a[:-2])<0]
``````

The input needs to be a Numpy array.

-

# C, 83

``````x,y,z;main(){y=z=0;while(scanf("%d",&x)){(y-z)*(y-x)>0?printf("%d ",y):1;z=y,y=x;}}
``````
-

## PHP, 116 114 113

``````function _(\$a){for(;\$a[++\$i+1];)if((\$b=\$a[\$i])<(\$c=\$a[\$i-1])&\$b<(\$d=\$a[\$i+1])or\$b>\$c&\$b>\$d)\$r[]=\$a[\$i];return\$r;}
``````

Example usage:

``````print_r(_(array(2, 1, 2, 3, 4, 3, 2, 3, 4)));

Array
(
[0] => 1
[1] => 4
[2] => 2
)
``````
-

APL - 19 chars

{⍵/⍨0,⍨0,0>2×/2-/⍵}

I converted the 20 char J version to APL. But I add a zero to the beginning and the end instead of removing the first and last digit. Otherwise it works just like the J version.

⍵ - formal parameter omega. This is the input to the function.

-
While we're at it, I have a K version, too, in 22 characters: `{x@1+&0>2_*':-':0 0,x}`. 6 of these characters (`2_` and `0 0,`) are spent protecting against a length error if the argument is shorter than two items, so if not for that problem it would be 16... The action is also a little different--we have to turn the boolean list into a list of indices with `1+&` and use that to index `x` again--but it's shorter and also a very K-ish thing to do. – algorithmshark Feb 27 '14 at 15:45
Your K version would beat my APL version then. My code needs at least two numbers. – user10639 Feb 28 '14 at 9:09

# awk - 32 chars

``````{c=b;b=a;a=\$0;\$0=b}(b-c)*(a-b)<0
``````

No hope of beating a language like J or APL on brevity, but I thought I'd throw my hat into the ring anyway. Explanation:

• At any given time, `a`, `b`, and `c` hold `x_i`, `x_(i-1)`, and `x_(i-2)`
• `b-c` and `a-b` approximate the derivative before and after `x_(i-1)`
• If their product is negative, then one is negative and the other is positive, therfore `x_(i-1)` is a local extreme, so print
-

Golfed version

``````e(a:b:c:r)
|a<b&&b>c||a>b&&b<c=b:s
|True=s
where s=e(b:c:r)
e _=[]
``````

Ungolfed version

``````-- if it's possible to get three elements from the list, take this one
extrema (a:b:c:rest)
| a<b && b>c = b:rec
| a>b && b<c = b:rec
| otherwise = rec
where rec = extrema (b:c:rest)
-- if there are fewer than three elements in the list, there are no extrema
extrema _ = []
``````
-

# Javascript: 102 characters

``````function h(a){for(u=i=[];++i<a.length-1;)if(x=a[i-1],y=a[i],z=a[i+1],(x-y)*(y-z)<0)u.push(y);return u}
``````
-