mediumArraysPattern: Modified Binary Search
Peak Element in Rotated Array Solution
Problem Statement
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
Example 1:
Input:[1, 3, 2, 5, 4]
Output:3
Explanation: The mass at index 3 is greater than its neighboring masses
Example 2:
Input:[5, 4, 3, 2, 1]
Output:0
Explanation: The mass at index 0 is greater than its neighboring mass
Example 3:
Input:[1, 2, 3, 4, 5]
Output:4
Explanation: The mass at index 4 is greater than its neighboring mass
Constraints
- 1 <= array length <= 10^5
- All elements in the array are unique and within the range of 1 to 10^9
Time: O(log n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.