Peak element
https://www.geeksforgeeks.org/problems/peak-element
https://leetcode.com/problems/find-peak-element
Difficulty: Basic
Accuracy: 38.86%
Submissions: 510K+Points: 1
Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return index of any one of them. The output will be “true” if the index returned by your function is correct; otherwise, it will be “false”.
Note: Consider the element before the first element and the element after the last element to be negative infinity.
Examples :
Input: arr = [1, 2, 4, 5, 7, 8, 3] Output: true Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].
Input: arr = [10, 20, 15, 2, 23, 90, 80] Output: true Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6].
Input: arr = [1, 2, 3] Output: true Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.
Constraints:
1 ≤ arr.size() ≤ 106
-231 ≤ arr[i] ≤ 231 – 1
Solution in C++
Algorithm: Uses a binary search approach to find a peak element in O(log n) time complexity.
//
// Created by robert on 12/15/24.
//
#include <iostream>
#include <vector>
using namespace std;
int findPeakElement(const vector<int>& arr) {
int n = arr.size();
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the mid element is a peak
if ((mid == 0 || arr[mid] > arr[mid - 1]) &&
(mid == n - 1 || arr[mid] > arr[mid + 1])) {
return mid; // Peak found
}
// If the left neighbor is greater, search on the left side
if (mid > 0 && arr[mid - 1] > arr[mid]) {
high = mid - 1;
}
// Otherwise, search on the right side
else {
low = mid + 1;
}
}
return -1; // This should never be reached
}
int main() {
vector<int> arr = {1, 2, 4, 5, 7, 8, 3};
int peakIndex = findPeakElement(arr);
cout << "Peak element index: " << peakIndex << endl;
return 0;
}