C++ Code To Count Local Extrema Of Given Array

Extrema are numerical values that represent either the lowest or highest point. In simpler terms, they are values that are either greater or smaller than adjacent values. Let's consider an array A with n elements. A specific element A[i] in this array is regarded as a local minimum only if it is smaller than both of its neighboring elements. Conversely, a local maximum exists if it is larger than its neighboring elements. Since they each have only one neighbor, the elements A[0] and A[n-1] do not qualify as either maxima or minima. Our task is to ascertain the total count of local extrema present in the given 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 employ a for loop to cycle through the items in the array beginning from the second one and concluding with the second-to-last one. By doing so, we ensure that the first and last elements are never at the edges. Utilizing both the for loop and if statements, we will determine whether each item is larger or smaller than both adjacent elements. Meeting either of these conditions leads to a single increment 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 method, we can leverage the maximum and minimum functionalities of the STL (Standard Template Library) algorithms. Specifically, built-in functions like std::max and std::min are employed to retrieve the highest and lowest values within a specified array range.

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:

• ✅ Initial: The element's beginning of the interval is determined by its position.
• ✅ Final: The element's position at the conclusion of the range is considered the last point.

For std::max({item 1, item 2, item 3}): All three items, including the present item and its adjacent neighbors, are crucial for identifying the local extrema collectively. This range consists of three items, hence the application of curly braces to indicate them.

Here, we iterate over the loop starting from the second to the penultimate element in the given array. Within the context of x[i - 1], x[i], and x[i + 1], we identify the highest and lowest elements. The count is incremented by one if the current element matches either of these two elements.

Example:

Let's consider an illustration to calculate the local extrema of a provided 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 summary, we explored different techniques for identifying the local extrema in an array. The initial strategy we covered was the fundamental iterative approach that employs a for loop. The alternative method involved the application of the std::min and std::max functions.