A peak is an element strictly greater than its neighbours. Given an array nums where no two adjacent values are equal, return the index of any peak. Treat the positions just outside the array as negative infinity, so the first or last element can be a peak. Aim for O(log n).
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- `nums[i] != nums[i + 1]` for every valid i
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The linear solution returns the first index where the values start falling, O(n). The trick for O(log n) is that we do not need the array to be sorted, we only need a rule that tells us which half surely contains a peak. If nums[mid] < nums[mid + 1] we are on an upward slope; following it to the right must end at a peak, since the edge counts as negative infinity. If nums[mid] > nums[mid + 1], then mid itself or something to its left is a peak. Halving the range each time finds one.
Algorithm
- Set
lo = 0,hi = n - 1. - While
lo < hi, computemid(notemid + 1 <= hi, so it is valid). - If
nums[mid] < nums[mid + 1], a peak is to the right:lo = mid + 1. - Otherwise a peak is at
midor to its left:hi = mid. - Return
lo.
O(log n)Space: O(1)class Solution: def findPeakElement(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] < nums[mid + 1]: lo = mid + 1 # uphill: a peak is to the right else: hi = mid # downhill: peak at mid or to its left return lo