C++ Code To Count Local Extrema Of Given Array

Extrema are such numbers that either have a minimum or a maximum. In other words, it refers to a value or element that is either larger or smaller than both of its neighboring values. Assume we have n elements in the array A. A local minimum is an element of this arrayof A[i] if and only if it is strictly less than both of its neighbors. A local maximum will also be reached if it is strictly greater than its neighbors. As they have a single neighbor, A[0] and A[n-1] are neither maxima nor minima. We must determine the number of local extrema within the provided array.

Example:

Input: Numbers={1,2,3}
Output:0
Input: Numbers={1,2,3,2,4,3,1}
Output: 3
Input: Numbers={1,3,2,4,5,3,6}
Output: 4

Approach 1: Using For Loop

We will use a for loop to iterate through the elements of the array starting from the second and ending with the second-to-last. This prevents the first and last elements from ever being at extremes. We will use the for loop and if statements to find out if each element is greater or less than both of its neighboring elements. Either of the two conditions results in a one-time increase in the variable num.

Example:

#include <iostream>
using namespace std;
// Function to count local extrema in an array
int countLocalExtrema(int arr[], int size) {
    int count = 0;
    // Iterate over the array from the second to the second last element
    for (int i = 1; i < size - 1; i++) {
        // Check if the current element is a local extremum
        if ((arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ||
            (arr[i] < arr[i - 1] && arr[i] < arr[i + 1])) {
            count++;
        }
    }
    return count;
}

int main() {
    // Example array
    int arr[] = {5, 10, 8, 3, 15, 9}; // Modify the array as needed for us 
    int size = sizeof(arr) / sizeof(arr[0]);
    // Count local extrema in the array
    int extremaCount = countLocalExtrema(arr, size);
    // Output the result
    std::cout << "Number of local extrema in the array: " << extremaCount << std::endl;
    return 0;
}

Output:

Number of local extrema in the array: 3

Approach 2: C++ Standard Template Library

In this approach, we may make use of the STL (Standard Template Library) algorithm's maximum and minimum operations. Predefined functions called std::max and std::min are utilised to return the largest and smallest element of a given range of an array.

Syntax:

It has the following syntax:

std::max_element(first, last)
std::min_element(first, last)
std::max({element 1, element 2, element 3});

Parameters:

• ✅ First: The element's starting point for the range is its position.
• ✅ Last: The element's location at the end of the range is the last.

For std::max({element 1, element 2, element 3}): The current element and both of its neighbors are the three elements we must take into consideration at once in order to locate the local extrema. Thus, we have three elements in our range. Because of this, we use curly braces to specify those three items.

Here, we repeat the loop from the second to the last element in the supplied array. Among x[i - 1], x[i], and x[i + 1], we determine the maximum and minimum element. Number is increased by one if the current element equals either of the two.

Example:

Let us take an example to count local extrema of a given array in C++.

#include <iostream>
#include <algorithm>
using namespace std;

// Function to count local extrema in an array
int countLocalExtrema(int arr[], int size) {
    int count = 0;
    // Iterate over the array from the second to the second last element
    for (int i = 1; i < size - 1; i++) {
        int max_element = std::max({arr[i - 1], arr[i], arr[i + 1]});
        int min_element = std::min({arr[i - 1], arr[i], arr[i + 1]});
        if (arr[i] == max_element || arr[i] == min_element) {
            count++;
        }
    }
    return count;
}

int main() {
    // Example array
    int arr[] = {7, 14, 9, 3, 21, 35}; // Modify the array as needed
    int size = sizeof(arr) / sizeof(arr[0]);

    // Count local extrema in the array
    int extremaCount = countLocalExtrema(arr, size);

    // Output the result
    std::cout << "Number of local extrema in the array: " << extremaCount << std::endl;

    return 0;
}

Output:

Number of local extrema in the array: 2

Conclusion:

In conclusion, we discussed about various methods for locating the local extrema within an array. We learned about the basic iterative method in the first approach, which uses a for loop. In the second method, we have utilized the std::min and std::max functions.