Find Peak Element
Find any peak (greater than both neighbors) in O(log n) using binary search on the slope.
3 min read
binary-search
Problem#
nums[i] != nums[i+1]. Return the index of any peak (greater than both neighbors). Boundaries are treated as -∞.
Examples#
[1,2,3,1]→2[1,2,1,3,5,6,4]→1or5
Constraints#
1 <= n <= 1000.
Approach#
Binary search. At each mid, compare nums[mid] to nums[mid+1]. If ascending (nums[mid] < nums[mid+1]), a peak must lie to the right. Else (descending or equal), to the left or at mid.
Solution#
class Solution {public: int findPeakElement(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[mid + 1]) lo = mid + 1; else hi = mid; } return lo; }};func findPeakElement(nums []int) int { lo, hi := 0, len(nums)-1 for lo < hi { mid := lo + (hi-lo)/2 if nums[mid] < nums[mid+1] { lo = mid + 1 } else { hi = mid } } return lo}from typing import List
class Solution: def findPeakElement(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] < nums[mid + 1]: lo = mid + 1 else: hi = mid return lofunction findPeakElement(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < nums[mid + 1]) lo = mid + 1; else hi = mid; } return lo;}class Solution { public int findPeakElement(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[mid + 1]) lo = mid + 1; else hi = mid; } return lo; }}function findPeakElement(nums: number[]): number { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < nums[mid + 1]) lo = mid + 1; else hi = mid; } return lo;}Editorial#
The “follow the gradient up” argument: an ascending slope guarantees a peak somewhere to the right (eventually we’ll descend or hit the boundary, which is -∞). Descending slope means a peak is to the left or at mid itself.
Complexity#
- Time: O(log n).
- Space: O(1).
Concept revision#
Related#