Problem 1

Find a peak element which is not smaller than its neighbors?

Given an array of integers, find a ‘peak’ element in the array. A peak element is defined as an element in the array that is greater than or equal to its neighbors. In other words, It is an element that is not smaller that the elements immediately to its left and right (if they exist). There can be multiple peak elements in an array.

Example1

Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: 3 is a peak element, and your function should return the index number 2.

Example2

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Explanation:

Brute force approach

A simple approach is to scan the array elements and check if their neighbors are strictly smaller. For the first and last element of the array, we verify the first index, and the second last index respectively. For the rest of the elements, we verify the neighbors.

Since we are scanning all the elements of the array, the time complexity of the code will be O(N)

#include <iostream>

int findPeak(int arr[], int n) {
    if (n == 0) {
        return -1;  // Array is empty
    }

    // Check the first element
    if (arr[0] >= arr[1]) {
        return arr[0];
    }

    // Check the last element
    if (arr[n - 1] >= arr[n - 2]) {
        return arr[n - 1];
    }

    // Iterate through the array to find a peak element
    for (int i = 1; i < n - 1; i++) {
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
            return arr[i];
        }
    }

    return -1;  // No peak element found
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peak = findPeak(arr, n);
    if (peak != -1) {
        std::cout << "A peak element is " << peak << std::endl;
    } else {
        std::cout << "No peak element found" << std::endl;
    }

    return 0;
}

// Output
A peak element is 20

Binary search approach

We can reduce the time complexity of the above program to O(log(N)) using binary search.

In the case of Binary search, we work on sorted array and try to find the target element by reducing the array size to half in every iteration. We can modify the Binary search approach for this problem to find the required element. If the middle element is not the peak, we can check if the element on the right side is greater than the middle element. If yes, there is always a peak element on the right side. Similarly, if the left side element is greater, the peak will be on the left side.

#include <iostream>
using namespace std;

int findPeak(int arr[], int size) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        // Check if arr[mid] is a peak element
        if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
            (mid == size - 1 || arr[mid + 1] <= arr[mid])) {
            return arr[mid];
        }
        // If arr[mid-1] is greater, search the left subarray
        if (mid > 0 && arr[mid - 1] > arr[mid]) {
            high = mid - 1;
        }
        // Otherwise, search the right subarray
         else {
            low = mid + 1;
        }
    }
    // No peak found
    return -1;
}

int main() {
    int arr[] = {1,2,7,4,5,6,25,4,75,5,45,6};
    int size = sizeof(arr) / sizeof(arr[0]);

    int index = findPeak(arr, size);
    cout << "element is = " << index;
}

// Output
element is = 75

If we need to get all the peak elements in an array, we can iterate throughout the array to find all of them. So in this case complexity becomes O(n). For e.g.,

#include <iostream>

using namespace std;

void findPeaks(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        if ((i == 0 || arr[i - 1] <= arr[i]) && (i == size - 1 || arr[i + 1] <= arr[i])) {
            // Element at index 'i' is a peak
            cout << "Peak at index " << i << ": " << arr[i] << endl;
        }
    }
}

int main() {
    int arr[] = {1, 3, 20, 4, 5, 0};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "All peak elements in the array:" << endl;
    findPeaks(arr, size);

    return 0;
}

// Output
All peak elements in the array:
Peak at index 2: 20
Peak at index 4: 5

Problem 2

Find the minimum or maximum element of an array.

There are several ways to solve this problem.

Linear Search

• Traverse the entire array, comparing each element to the current minimum and maximum.
• Initialize the minimum and maximum as the first element in the array.
• Update the minimum and maximum as you iterate through the array.
• Time Complexity: O(n) - where ‘n’ is the number of elements in the array.

#include <iostream>

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    int min_element = arr[0];
    int max_element = arr[0];

    for (int i = 1; i < n; i++) {
        if (arr[i] < min_element) {
            min_element = arr[i];
        }
        if (arr[i] > max_element) {
            max_element = arr[i];
        }
    }

    std::cout << "Minimum element: " << min_element << std::endl;
    std::cout << "Maximum element: " << max_element << std::endl;

    return 0;
}

// Output
Minimum element: 1
Maximum element: 9

Sorting

• Sort the array in ascending or descending order using a sorting algorithm like quicksort or mergesort.
• The minimum element will be the first element of the sorted array and the maximum element will be the last element.
• Time Complexity: O(n log(n)) - where ‘n’ is the number of elements in the array.

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::sort(arr, arr + n);

    int min_element = arr[0];
    int max_element = arr[n - 1];

    std::cout << "Minimum element: " << min_element << std::endl;
    std::cout << "Maximum element: " << max_element << std::endl;

    return 0;
}

// Output
Minimum element: 1
Maximum element: 9

Divide and Conquer (Recursive)

• Divide the array into two halves recursively until you have subarrays of size 1.
• Compare and merge the minimum and maximum of the subarrays as you merge them back together.
• Time Complexity: O(n) - where ‘n’  is the number of elements in the array. This is because it recursively divides the array into halves, and you do a constant amount of work at each level of recursion.

#include <iostream>

struct MinMax {
    int min;
    int max;
};

MinMax findMinMax(int arr[], int low, int high) {
    MinMax result;
    if (low == high) {
        result.min = arr[low];
        result.max = arr[low];
        return result;
    }

    int mid = (low + high) / 2;
    MinMax left = findMinMax(arr, low, mid);
    MinMax right = findMinMax(arr, mid + 1, high);

    result.min = std::min(left.min, right.min);
    result.max = std::max(left.max, right.max);

    return result;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    MinMax result = findMinMax(arr, 0, n - 1);

    std::cout << "Minimum element: " << result.min << std::endl;
    std::cout << "Maximum element: " << result.max << std::endl;

    return 0;
}

// Output
Minimum element: 1
Maximum element: 9