Search for local min / max in a 1D array / histogram

Question

I am trying to find the indices of all local minima and maxima inside an array.

Example:

int[] array = {5,4,3,3,3,3,3,2,2,2, 6,6,8,5,5,5,3,3,2,1, 1,4,4,7}; // | | | // Indices: 0,1,2,3,4,5,6,7,8,9, 10,1,2,3,4,5,6,7,8,9, 20,1,2,3 // Minima: 8, 20 // Maxima: 12 

I came up with an algorithm about which I have a few questions left:

• Is there much better? :)
• I used Enum with methods to achieve this dualism that UP and STRAIGHT_UP are "UP". Seems dirty to me. Any suggestions?
• Do you have better method names? direction () (+ return value) implies that STRAIGHT is not a directory. But at the same time it is, since it is an element in Emum. Hm.
• It works for a given array. Do you see a situation where this is not so?

-

 import java.util.ArrayList; public class MinMaxFinder { private int[] array; private ArrayList<Integer> minima; private ArrayList<Integer> maxima; private enum Direction{ UP, DOWN, STRAIGHT_UP, STRAIGHT_DOWN, STRAIGHT; public Direction direction(){ if(this==UP || this==STRAIGHT_UP){ return UP; }else if(this==DOWN || this==STRAIGHT_DOWN){ return DOWN; }else{ return STRAIGHT; } } public boolean isStraight(){ if(this==STRAIGHT_DOWN || this==STRAIGHT_UP || this==STRAIGHT){ return true; }else{ return false; } } public boolean hasDifferentDirection(Direction other){ if(this!=STRAIGHT && other!=STRAIGHT && this.direction() != other.direction() ){ return true; } return false; } } public MinMaxFinder(int[] array){ this.array = array; } public void update() { minima = new ArrayList<Integer>(); maxima = new ArrayList<Integer>(); Direction segmentDir = Direction.DOWN; int indexOfDirectionChange = 0; int prevVal = array[0]; int arrayLength = array.length; for(int i=1; i<arrayLength; i++){ int currVal = array[i]; Direction currentDir = currVal<prevVal?Direction.DOWN:(currVal>prevVal?Direction.UP:Direction.STRAIGHT); prevVal = currVal; if(currentDir.hasDifferentDirection(segmentDir)){ int changePos = (indexOfDirectionChange+i-1)/2; if(currentDir.direction() == Direction.DOWN){ maxima.add(changePos); }else{ minima.add(changePos); } segmentDir = currentDir; indexOfDirectionChange = i; }else if( currentDir.isStraight() ^ segmentDir.isStraight() ){ indexOfDirectionChange = i; if(currentDir.isStraight() && segmentDir.direction()==Direction.UP){ segmentDir=Direction.STRAIGHT_UP; }else if(currentDir.isStraight() && segmentDir.direction()==Direction.DOWN){ segmentDir=Direction.STRAIGHT_DOWN; }else{ segmentDir = currentDir; } } } } public ArrayList<Integer> getMinima() { return minima; } public ArrayList<Integer> getMaxima() { return maxima; } } 

Answer 1

I think I get it. Thank you, guys! Your ideas helped me a lot!

For me, the following solution will be executed:

  ArrayList<Integer> mins = new ArrayList<Integer>(); ArrayList<Integer> maxs = new ArrayList<Integer>(); int prevDiff = array[0] - array[1]; int i=1; while(i<array.length-1){ int currDiff = 0; int zeroCount = 0; while(currDiff == 0 && i<array.length-1){ zeroCount++; i++; currDiff = array[i-1] - array[i]; } int signCurrDiff = Integer.signum(currDiff); int signPrevDiff = Integer.signum(prevDiff); if( signPrevDiff != signCurrDiff && signCurrDiff != 0){ //signSubDiff==0, the case when prev while ended bcoz of last elem int index = i-1-(zeroCount)/2; if(signPrevDiff == 1){ mins.add( index ); }else{ maxs.add( index ); } } prevDiff = currDiff; } 

Answer 2

Consider the array of the first differences d[i] = a[i] - a[i-1] .

If d[i] positive, then a increased in the last step, and if d[i] negative, then a decreased. Thus, a change in the sign of d from positive to negative means that a increased, now decreased, locally max. Similarly, negative-positive indicates a local minimum.

Answer 3

Something like this “should” work, and it is probably conceptually less complicated. Scans an array once and registers minutes and maxs.

Worth mentioning:
1) It is possible that if (direction <0) {} else {} can be removed, but I did not have time to think about the details.
2) The main idea is that depending on the first "direction" (regardless of whether we see the minimum or maximum first), the order of the loops changes.
3) in case of several elements, it will always contain the last element (the highest index).

 if(a.length < 2){ return; } List<Integer> mins = new ArrayList<Integer>(); List<Integer> maxs = new ArrayList<Integer>(); int i=1; int prev = 0; int direction = 0; for(int j=1, k = 0;j<a.length && (direction = a[j]-a[k]) == 0;j++, k++); if(direction == 0){ //Array contains only same value. return; } if(direction < 0){ while(i<a.length){ for(;i<a.length && a[prev] >= a[i];i++,prev++); mins.add(prev); for(;i<a.length && a[prev] <= a[i];i++,prev++); maxs.add(prev); i++;prev++; } } else{ while(i<a.length){ for(;i<a.length && a[prev] <= a[i];i++,prev++); maxs.add(prev); for(;i<a.length && a[prev] >= a[i];i++,prev++); mins.add(prev); i++;prev++; } } //maxs and mins now contain what requested