JavaScript algorithms: how do I find all local max in an array

Question

Similar to this leetcode question https://leetcode.com/problems/find-peak-element/ but the returned result should be an array of the indices to all peaks or local max

E.g.

Given an array like this [1,2,1,3,5,6,4], I need to return [2, 5]

If we only return the one peak number, we can just use binary search to eliminate half of the array one time. Here is my solution

var findPeakElement = function(nums) {
    let left = 0, right = nums.length - 1
    
    while(left < right) {
        const mid = Math.floor((left + right) / 2)
        if(nums[mid] > nums[mid + 1]) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    
    return right
};

But now the question is asking to return all indices to the local max numbers. I cannot think of any other way other than iterate through the array and check the number one by one to see if it is bigger than its previous number and the next number.

Answer 1

You do have to scan the whole array, and it will take O (n) time to do so. A simple proof is that when you try [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, ..., 2, 1, 2], half your values will be local maxima, so any algorithm that checks this will take at least n / 2 operations (of some sort).

Here's a fairly simple version that reports all peaks, with separate handling for the first and the last indices, and common handling for the remainder. It assumes you only want true peaks and not plateaus. If you want plateau indices, you'll have to replace some < / > signs with <= / >= ones.

const localMaxima = (ns) => [
  ... (ns [0] > ns [1] ? [0] : []),
  ... Array .from ({length: ns.length - 1}, ((_, i) => i + 1)) 
        .filter ((i) => ns [i - 1] < ns [i] && ns [i + 1] < ns [i]),
  ... (ns [ns .length - 1] > ns [ns .length - 2] ? [ns .length - 1] : [])
]

console .log (localMaxima ([1, 2, 1, 3, 5, 6, 4])) //=> [1, 5]
//                             ^           ^
console .log (localMaxima ([8, 5, 7, 5, 3, 0, 9])) //=> [0, 2, 6]
//                          ^     ^           ^
console .log (localMaxima ([2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])) //=> [0, 2, 4, 6, 8, 10]
//                          ^     ^     ^     ^     ^     ^

.as-console-wrapper {max-height: 100% !important; top: 0}

Note that the first example returns [1, 5]. Was the [2, 5] in the question simply a typo?

Update

A comment asked to make this "more readable".

There is absolutely one thing I should have done. I inlined a range function here. There was no reason for that. It's much more readable when using a separate function. (range is a simple function to return an integer range. For instance range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12].)

Using that instead leads to what to me is a quite readable version:

const range = (lo, hi) => Array .from ({length: hi - lo + 1}, (_, i) => lo + i)

const localMaxima = (ns) => [
  ... (ns [0] > ns [1] ? [0] : []),
  ... range (1, ns.length - 2) .filter ((i) => ns [i - 1] < ns [i] && ns [i + 1] < ns [i]),
  ... (ns [ns .length - 1] > ns [ns .length - 2] ? [ns .length - 1] : [])
]

However, I don't think that's what's being asked. I think the sort of code requested might look something like this:

const localMaxima = (ns) => {
  const includeStart = ns [0] > ns [1]
  const includeEnd = ns [ns.length - 1] > ns [ns .length -2]
  const intermediates = range (0, ns .length - 2)
    .filter ((i) => ns [i - 1] < ns [i] && ns [i + 1] < ns [i])
  if (includeStart) intermediates .unshift (0)
  if (includeEnd) intermediates .push (ns .length - 1)
  return intermediates
}

But I don't like that at all. I try as best I can to work with immutable data, and the unshift and push calls are horrible to my eyes.

Probably the closest I could come to that and still look myself in the mirror is

const localMaxima = (ns) => {
  const includeStart = ns [0] > ns [1]
  const includeEnd = ns [ns.length - 1] > ns [ns .length -2]
  const intermediates = range (0, ns .length - 2)
    .filter ((i) => ns [i - 1] < ns [i] && ns [i + 1] < ns [i])
  const beginning = includeStart ? [0] : []
  const ending = includeEnd ? [ns .length - 1] : []
  return beginning .concat (intermediates) .concat (ending)
}

I'm also not much of a fan of these one-off variable assignments, but in languages like JS they are sometimes hard to avoid. At least here they're still const. I would avoid replacing this:

  const beginning = includeStart ? [0] : []

with this alternative

  let beginning
  if (includeStart) {
    beginning = [0]
  } else {
    beginning = []
  }

so if you simply don't like conditional operators (ternaries), we're probably never going to see eye-to-eye!

I would very much choose my post-range refactoring over these versions any day. But readability is in the eyes of the beholder, and perhaps this last one would make some happy.

Answer 2

As far as I can tell, your approach is correct. You do need to look at three values (current, previous, and next) in order to determine if a number is a local maximum.

Abstracting this away from JavaScript for a moment, and just thinking about it mathematically, finding a local maximum of a continuous function (which is an approximate model for this array of integers) means finding the points at which its first derivative (i.e. its gradient) is 0, and its second derivative (i.e. the gradient of the initial function's gradient) is negative. That is, the points where the function is flat, and curving downwards.

To find the derivative of a function numerically, you need to look at two points on the function. The same goes for finding the second derivative - you need to look at two points on the derivative function. Those two points in the derivative function were each calculated based on two points in the original function, but one of those points is shared so essentially you need to look at three points in the original function to find the second derivative.

Keep in mind though that you won't always need to do two comparisons. If a number is smaller than the number that came before, of course you don't need to check the next number because you already know you haven't found a local maximum. You may need to consider the edge case of having the same number come up multiple times in a row, however, and whether or not each of them should count as a local maximum.