Problem Statement:
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.
Approach:
- 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 →shift l = m + 1. - Else → we are in descending slope or peak →
move r = m. - Loop ends when
l == r, that’s the index of a peak.
Time & Space Complexity:
Time Complexity: O(logn)
Space Complexity: O(1)
Dry Run
Input: arr = [1, 3, 5, 4, 2]
Initial: l = 0, r = 4 arr = [1, 3, 5, 4, 2] Loop 1: m = 0 + Math.floor((4 - 0) / 2) = 2 arr[m] = 5, arr[m + 1] = 4 Check: arr[m] < arr[m + 1]? → 5 < 4 → false Else → r = m = 2 Loop 2: m = 0 + Math.floor((2 - 0) / 2) = 1 arr[m] = 3, arr[m + 1] = 5 Check: arr[m] < arr[m + 1]? → 3 < 5 → true So l = m + 1 = 2 Exit Condition: l = 2, r = 2 → l == r → stop Return l = 2 (index of peak element)
Output: Result: 2 (peak element = 5)
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;
};
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;
}
}
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;
}
}
