C++ Program for Number of local extrema in an array

Assume we have an n-element array A. A local minimum is an element of this array A[i] that is strictly smaller than both of its neighbours. It will also be the local maximum if it is strictly larger than its neighbours. Because A[0] and A[n-1] have just one neighbor, they are not maximum or minimum. The number of local extrema in the provided array must be determined.

So, if A = [1, 5, 2, 5], the output will be 2, since 5 at A[1] is a local maximum and 2 at A[2] is a local minimum.

Approach: To calculate the number of extrema, we must first determine if an element is maxima or minima, that is, whether it is more than or less than both of its neighbors. Cycle over the array, checking each element's likelihood of becoming an extrema.

It is worth noting that a[0] and a[n-1] each have precisely one neighbor and are neither minima nor maxima.

Example:

Filename: Extreme.cpp

Output:

2

Complexity Analysis:

Time complexity: O(n), where n is the length of the input array. It is due to the fact that a for loop executes from 1 to n.

Space Complexity: O(1) since no additional space was utilized.