Dare2Solve
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]
(for i > 0
) andnums[i] > nums[i + 1]
(for i < nums.length - 1
)The goal is to return the index of any peak element.
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.
Initialize Pointers:
l
(left) to 0 and r
(right) to nums.length - 1
.Binary Search:
l
is less than r
, calculate the middle index mid
of the current subarray.nums[mid]
with its right neighbor nums[mid + 1]
.
nums[mid + 1] > nums[mid]
, then the peak must be in the right half of the array, so update l
to mid + 1
.mid
, so update r
to mid
.Return Peak:
l
equals r
, return l
(or r
), which will be the index of the peak element.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.
O(1), as the algorithm uses a constant amount of extra space for pointers and variables.
class Solution {
public:
int findPeakElement(vector<int>& 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;
}
};
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
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;
}
}
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;
};