Find Peak in Rotated Sorted Array
EasyUpdated: Aug 10, 2025
Problem
Given an array that's sorted but rotated at some unknown pivot, in which all elements are distinct, find a "peak" element in O(log N) time.
An element is considered a peak if it is greater than both its left and right neighbors. It is guaranteed that the first and last elements are lower than all others.
Examples
Example 1
Input: [1, 3, 20, 4, 1, 0]
Output: 20
Explanation: 20 is greater than both neighbors 3 and 4, so it's a peak.
Example 2
Input: [2, 1, 3, 6, 5, 4]
Output: 6
Explanation: 6 is greater than both neighbors 3 and 5, so it's a peak.
Example 3
Input: [4, 5, 6, 7, 1, 2, 3]
Output: 7
Explanation: 7 is greater than both neighbors 6 and 1, so it's a peak.
Example 4
Input: [10, 20, 15, 2, 23, 90, 67]
Output: 20 or 90
Explanation: Both 20 (neighbors 10, 15) and 90 (neighbors 23, 67) are peaks.
Example 5
Input: [1, 2, 3]
Output: 2
Explanation: 2 is greater than both neighbors 1 and 3.
Solution
Method 1 - Binary Search Peak Finding
Intuition
In a rotated sorted array, we can use binary search to find a peak efficiently. The key insight is that if we're at a position where the element is smaller than its right neighbor, there must be a peak to the right. Similarly, if it's smaller than its left neighbor, there must be a peak to the left.
Approach
- Use binary search with left and right pointers
- At each middle position, compare the element with its neighbors
- If middle element is greater than both neighbors, it's a peak
- If middle element is smaller than right neighbor, search right half
- If middle element is smaller than left neighbor, search left half
- Continue until a peak is found
Code
C++
class Solution {
public:
int findPeak(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
int left = 1, right = n - 2;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
return nums[mid];
}
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Should not reach here given problem constraints
}
};
Go
func findPeak(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
if n == 2 {
if nums[0] > nums[1] {
return nums[0]
}
return nums[1]
}
left, right := 1, n-2
for left <= right {
mid := left + (right-left)/2
if nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] {
return nums[mid]
}
if nums[mid] < nums[mid+1] {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // Should not reach here given problem constraints
}
Java
class Solution {
public int findPeak(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0], nums[1]);
int left = 1, right = n - 2;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
return nums[mid];
}
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Should not reach here given problem constraints
}
}
Python
class Solution:
def findPeak(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
left, right = 1, n - 2
while left <= right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
return nums[mid]
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid - 1
return -1 # Should not reach here given problem constraints
Complexity
- ⏰ Time complexity:
O(log n), binary search eliminates half the search space in each iteration - 🧺 Space complexity:
O(1), only using constant extra space for variables
Method 2 - Rotation Point as Peak
Intuition
In a rotated sorted array, the maximum element (which was originally at the end) becomes a natural peak after rotation. We can find this rotation point efficiently using binary search, and it will always be a peak since it's the largest element.
Approach
- Find the rotation point (index of maximum element) using binary search
- The rotation point is where the array "breaks" its sorted order
- This maximum element is guaranteed to be a peak
- Use the fact that in a rotated sorted array, the maximum element is always greater than its neighbors
Code
C++
class Solution {
public:
int findPeakUsingRotation(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
// left points to minimum element, so maximum is at (left - 1 + n) % n
int maxIdx = (left - 1 + n) % n;
return nums[maxIdx];
}
};
Go
func findPeakUsingRotation(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
left, right := 0, n-1
for left < right {
mid := left + (right-left)/2
if nums[mid] > nums[right] {
left = mid + 1
} else {
right = mid
}
}
// left points to minimum element, so maximum is at (left - 1 + n) % n
maxIdx := (left - 1 + n) % n
return nums[maxIdx]
}
Java
class Solution {
public int findPeakUsingRotation(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
// left points to minimum element, so maximum is at (left - 1 + n) % n
int maxIdx = (left - 1 + n) % n;
return nums[maxIdx];
}
}
Python
class Solution:
def findPeakUsingRotation(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
left, right = 0, n - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
# left points to minimum element, so maximum is at (left - 1 + n) % n
max_idx = (left - 1 + n) % n
return nums[max_idx]
Complexity
- ⏰ Time complexity:
O(log n), binary search to find rotation point - 🧺 Space complexity:
O(1), constant extra space usage