Peak Element in Rotated Array ā Problem Statement & Solution Guide
Problem Description
You are given a rotated sorted array of unique integers. Find the index of the peak element, which is the element that is greater than its neighbors.
Examples
Input
[3, 4, 5, 1, 2]
Output
2
Explanation: Step-by-step: The given array is [3, 4, 5, 1, 2]. We first find the peak element in the array, which is 5. The index of the peak element is 2.
Input
[1, 2, 3, 4, 5]
Output
4
Explanation: Step-by-step: The given array is [1, 2, 3, 4, 5]. We first find the peak element in the array, which is 5. The index of the peak element is 4.
Constraints
- 1 <= array length <= 10^5
- All elements in the array are unique and within the range of 1 to 10^9
Optimal Approach & Strategy
The optimal approach involves using a modified binary search algorithm to find the peak element in the distorted galaxy map. This approach takes advantage of the fact that the array is rotated and has a peak element, allowing it to find the solution in O(log n) time complexity.
Brute Force Approach
The brute-force approach involves iterating through the array and checking each element to see if it is the peak element. This approach has a time complexity of O(n) but is not efficient for large arrays. A naive approach would be to compare each element with its neighbors, resulting in a time complexity of O(nĀ²).
Verified Code Solutions
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return leftAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.