This problem involves finding any **peak element** in an array. A peak element is an element that is strictly greater than its neighbors. The array is unsorted, but there’s guaranteed to be at least one peak.
Steps
- We use binary search to find a peak efficiently.
- Initialize
l = 0andr = arr.length - 1. - While
l < r:- Find middle:
m = l + floor((r - l) / 2) - If
arr[m] < arr[m + 1]→ we are in ascending slope → shiftl = m + 1 - Else → we are in descending slope or peak → move
r = m
- Find middle:
- Loop ends when
l == r, that’s the index of a peak.
Dry Run
Input: [12, 3, 1]
- m = 1 → 3 < 1 → r = 1
- m = 0 → 12 > 3 → r = 0
- l == r == 0 → return 0
Output: 0 (12 is a peak)
Input: [1,2,1,3,5,6,4]
There are multiple peaks possible, e.g. index 1 (2), 5 (6)
Output: 5 (or any valid peak index)
Time & Space Complexity
- Time Complexity: O(log n) — binary search used
- Space Complexity: O(1)
var findPeakElement = function(arr) {
let l = 0;
let r = arr.length - 1;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (arr[m] < arr[m + 1]) {
l = m + 1;
} else {
r = m;
}
}
return l;
};
int findPeakElement(vector& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] < arr[m + 1]) l = m + 1;
else r = m;
}
return l;
}
int findPeakElement(int* arr, int arrSize) {
int l = 0, r = arrSize - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] < arr[m + 1]) l = m + 1;
else r = m;
}
return l;
}
public class Solution {
public int findPeakElement(int[] arr) {
int l = 0, r = arr.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] < arr[m + 1]) l = m + 1;
else r = m;
}
return l;
}
}
def findPeakElement(arr):
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l) // 2
if arr[m] < arr[m + 1]:
l = m + 1
else:
r = m
return l
public class Solution {
public int FindPeakElement(int[] arr) {
int l = 0, r = arr.Length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] < arr[m + 1]) l = m + 1;
else r = m;
}
return l;
}
}
