
Description
The problem is to find a peak element in an array. A peak element is an element that is greater than its neighbors. For an array nums
, an element nums[i]
is a peak if:
nums[i] > nums[i - 1]
(fori > 0
) andnums[i] > nums[i + 1]
(fori < nums.length - 1
)
The goal is to return the index of any peak element.
Intuition
To efficiently find a peak element, we can use a modified binary search. This approach exploits the fact that if the middle element of a subarray is not a peak, then at least one of its neighbors must be greater. Therefore, we can move our search to the half of the array where the neighbor is greater.
Approach
- Initialize Pointers:
- Set two pointers:
l
(left) to 0 andr
(right) tonums.length - 1
. - Binary Search:
- While
l
is less thanr
, calculate the middle indexmid
of the current subarray. - Comparenums[mid]
with its right neighbornums[mid + 1]
. - Ifnums[mid + 1] > nums[mid]
, then the peak must be in the right half of the array, so updatel
tomid + 1
. - Otherwise, the peak is in the left half or atmid
, so updater
tomid
. - Return Peak:
- When
l
equalsr
, returnl
(orr
), which will be the index of the peak element.
Complexity
Time Complexity:
O(log n), where n
is the number of elements in the array. This is due to the binary search approach, which halves the search space with each iteration.
Space Complexity:
O(1), as the algorithm uses a constant amount of extra space for pointers and variables.
Code
C++
class Solution {
public:
int findPeakElement(vector& nums) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid + 1] > nums[mid]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
};
Python
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid + 1] > nums[mid]:
l = mid + 1
else:
r = mid
return l
Java
class Solution {
public int findPeakElement(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid + 1] > nums[mid]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
}
JavaScript
var findPeakElement = function (nums)
{
let l = 0;
let r = nums.length - 1;
while (l < r) {
const mid = Math.floor((l + r) / 2);
if (nums[mid + 1] > nums[mid]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
};