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

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.

CodePudding user response：

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.

CodePudding user response：

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?