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

1
2
3

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

1
2
3

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

1
2
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

1
2
3

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

1
2
3

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

  1. Use binary search with left and right pointers
  2. At each middle position, compare the element with its neighbors
  3. If middle element is greater than both neighbors, it’s a peak
  4. If middle element is smaller than right neighbor, search right half
  5. If middle element is smaller than left neighbor, search left half
  6. Continue until a peak is found

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

  1. Find the rotation point (index of maximum element) using binary search
  2. The rotation point is where the array “breaks” its sorted order
  3. This maximum element is guaranteed to be a peak
  4. Use the fact that in a rotated sorted array, the maximum element is always greater than its neighbors

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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