Finding the local maxima in a 1D array

Question

Is there an easy way to find the local maxima in a 1D array?

Let's say I have an array:

[ 0,
  1,
  10, <- max
  8,  <- (ignore)
  3,
  0,
  0,
  4,
  6,  <- (ignore)
  10, <- max
  6,  <- (ignore)
  1,
  0,
  0,
  1,
  4,  <- max
  1,
  0 ]

I want it to find the 10s and the 4, but ignore the 8 & 6, since those are next to 10s. Mathematically, you could just find where derivative is equal to zero if it were a function. I'm not too sure how to do this in Javascript.

Answer 1

const values = [3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3];

const findMinimas = arr => arr.filter((el, index) => {
  return el < arr[index - 1] && el < arr[index + 1]
});
  
console.log(findMinimas(values)); // => [2, 1, 1]

const findMinimumIndices = arr => arr.map((el, index) => {
  return el < arr[index - 1] && el < arr[index + 1] ? index : null
}).filter(i => i != null);
  
console.log(findMinimumIndices(values)); // => [1, 5, 9]

Answer 2

A Python implementation, with a couple of points

• Avoids using a reduce to make it easier to see the algorithm
• First and last items are considered peaks (this can be a requirement, e.g. in interviews)
• All values in the plateau are added
• Can start or end on an plateau

def findPeaks(points: List[int]) -> List[int]:
    peaks, peak = [], []

    if points[0] >= points[1]:  # handle first
        peak.append(points[0])

    for i in range(1, len(points)):
        prv = points[i - 1]
        cur = points[i]

        if cur > prv:  # start peak
            peak = [cur]
        elif cur == prv:  # existing peak (plateau)
            peak.append(cur)
        elif cur < prv and len(peak):  # end peak
            peaks.extend(peak)
            peak = []

    if len(peak) and len(peak) != len(points):  # ended on a plateau
        peaks.extend(peak)

    return peaks

if __name__ == "__main__":
    print(findPeaks([1, 2, 3, 4, 5, 4, 3, 2, 1]))   # [5]
    print(findPeaks([1, 2, 1, 2, 1]))               # [2, 2]
    print(findPeaks([8, 1, 1, 1, 1, 1, 9]))         # [0, 6]
    print(findPeaks([1, 1, 1, 1, 1]))               # []
    print(findPeaks([1, 6, 6, 6, 1]))               # [6, 6, 6]

Answer 3

The two situations are when you have a peak, which is a value greater than the previous and greater than the next, and a plateau, which is a value greater than the previous and equal to the next(s) until you find the next different value which must me less.

so when found a plateau, temporary create an array from that position 'till the end, and look for the next different value (the Array.prototype.find method returns the first value that matches the condition ) and make sure it is less than the first plateau value.

this particular function will return the index of the first plateau value.

function pickPeaks(arr){
  return arr.reduce( (res, val, i, self) => {
    if(
      // a peak when the value is greater than the previous and greater than the next
      val > self[i - 1] && val > self[i + 1] 
      || 
      // a plateau when the value is greater than the previuos and equal to the next and from there the next different value is less
      val > self[i - 1] && val === self[i + 1] && self.slice(i).find( item =>  item !== val ) < val 
    ){
      res.pos.push(i);
      res.peaks.push(val);
    }
    return res;
  }, { pos:[],peaks:[] } );
}

console.log(pickPeaks([3,2,3,6,4,1,2,3,2,1,2,3])) //{pos:[3,7],peaks:[6,3]}
console.log(pickPeaks([-1, 0, -1])) //{pos:[1],peaks:[0]}
console.log(pickPeaks([1, 2, NaN, 3, 1])) //{pos:[],peaks:[]}
console.log(pickPeaks([1, 2, 2, 2, 1])) //{pos: [1], peaks: [2]} (plateau!)

Answer 4

This will return an array of all peaks (local maxima) in the given array of integers, taking care of the plateaus as well:

function findPeaks(arr) {
  var peak;
  return arr.reduce(function(peaks, val, i) {
    if (arr[i+1] > arr[i]) {
      peak = arr[i+1];
    } else if ((arr[i+1] < arr[i]) && (typeof peak === 'number')) {
      peaks.push(peak);
      peak = undefined;
    }
    return peaks;
  }, []);
}

findPeaks([1,3,2,5,3])   // -> [3, 5]
findPeaks([1,3,3,3,2])   // -> [3]
findPeaks([-1,0,0,-1,3]) // -> [0]
findPeaks([5,3,3,3,4])   // -> []

Note that the first and last elements of the array are not considered as peaks, because in the context of a mathematical function we don't know what precedes or follows them and so cannot tell if they are peaks or not.

Answer 5

more declarative approach:

const values = [3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3];

const findPeaks = arr => arr.filter((el, index) => {
  return el > arr[index - 1] && el > arr[index + 1]
});
  
console.log(findPeaks(values)); // => [6, 3]

Answer 6

This code finds local extrema (min and max, where first derivation is 0, and ), even if following elements will have equal values (non-unique extrema - ie. '3' is choosen from 1,1,1,3,3,3,2,2,2)

var GoAsc  = false;      //ascending move
var GoDesc = false;      //descending move
var myInputArray = [];
var myExtremalsArray = [];
var firstDiff;

for (index = 0; index < (myArray.length - 1); index++) {
    //(myArray.length - 1) is because not to exceed array boundary, 
    //last array element does not have any follower to test it

  firstDiff = ( myArray[index] - myArray[index + 1] );

   if ( firstDiff > 0 )   { GoAsc  = true;  }
   if ( firstDiff < 0 )   { GoDesc = true;  }

   if ( GoAsc === true && GoDesc === true )  {  
        myExtremalsArray.push(myArray[index]);
        GoAsc  = false ;     
        GoDesc = false;     
        //if firstDiff > 0 ---> max
        //if firstDiff < 0 ---> min
      }

 }

Answer 7

How about a simple iteration?

var indexes = [];
var values = [0,1,10,8,3,0,0,4,6,10,6,1,0,0,1,4,1,0];
for (var i=1; i<values.length-1; i++)
    if (values[i] > values[i-1] && values[i] > values[i+1])
        indexes.push(i);

Answer 8

maxes = []
for (var i = 1; i < a.length - 1; ++i) {
    if (a[i-1] < a[i] && a[i] > a[i+1])
        maxes.push(a[i])
}