Sponsored
Sponsored
The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.
Time Complexity: O(log n), Space Complexity: O(1)
1def findPeakElement(nums):
2 left, right = 0, len(nums) - 1
3 while left < right:
4 mid = (left + right) // 2
5 if nums[mid] > nums[mid + 1]:
6 right = mid
7 else:
8 left = mid + 1
9 return left
10
11nums = [1, 2, 3, 1]
12index = findPeakElement(nums)
13print(f"Peak element index: {index}")This Python solution employs a binary search method. The 'while' loop continues until the search space is reduced to a single element. We adjust either the 'right' or 'left' index by evaluating the mid-element and its right neighbor
Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.
Time Complexity: O(n), Space Complexity: O(1)
1
In this approach, we first handle edge cases for the start and end of the array. Then, we iterate through the array to find the first element greater than its neighbors. While the time complexity is O(n), it provides a straightforward implementation.