Consider an array A with n elements. In this context, a local minimum is defined as an element A[i] in the array that is smaller than its neighboring elements. Similarly, a local maximum is an element that is larger than its neighbors. It is important to note that the first and last elements of the array, A[0] and A[n-1], respectively, are not considered local extrema due to having only one neighbor. The task at hand is to ascertain the total count of local extrema present in the given array.
So, if A = [1, 5, 2, 5], the result will be 2, as the number 5 at A[1] represents a local maximum, and the number 2 at A[2] represents a local minimum.
Approach: In order to ascertain the count of extremities, the initial step involves identifying whether an item qualifies as a maximum or minimum, indicating if it surpasses or falls short of both adjacent elements. Iterate through the array, evaluating the potential for each element to serve as an extremum.
It is important to highlight that a[0] and a[n-1] both have exactly one adjacent element and do not qualify as minimum or maximum values within the array.
Example:
Filename: Extreme.cpp
// Program to find the local extreme value
#include <bits/stdc++.h>
using namespace std;
// function for finding the loacl maximum value
int extrema(int arr[], int num)
{
int c = 0;
// ierate a loop upto num-1 times
for (int i = 1; i < num - 1; i++)
{
// Only one criterion will be true at any one time: arr[i] must be bigger than or less than its neighbors.
// If arr[i] is bigger than both of its neighbors, add 1 to x.
c += (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]);
//If a[i] is less than both of its // neighbors, then add 1 to x.
c += (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]);
}
return c;
}
// Main
int main()
{
int arr[] = { 2, 5, 1, 6 };
int num = sizeof(arr) / sizeof(arr[0]);
cout << extrema(arr, num);
return 0;
}
Output:
Complexity Analysis:
The time complexity is O(n), with 'n' representing the size of the input array. This is because a for loop runs from 1 to n in this scenario.
Space Complexity: O(1) as no extra space was allocated.
