Find Peak Element
Problem statement
You're given a list of numbers, nums, where no two neighbors are ever equal. A peak is a value that is strictly bigger than both of the values right next to it. Find the index of any one peak and return it — if several peaks exist, any one of their indices is an acceptable answer.
To make the two ends of the list simple to reason about, imagine there's an invisible -infinity sitting just before index 0 and just after the last index. That means the first element only has to beat its one real neighbor to count as a peak, and the same goes for the last element.
The array isn't sorted and doesn't have to look like a single hill — it can zig-zag up and down several times — but you still need to find a peak in O(log n) time, not by looking at every value.
Examples
Example 1
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 (at index 2) is bigger than both of its neighbors, 2 and 1, so it's a peak.
Example 2
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: 6 (at index 5) is bigger than both of its neighbors, 5 and 4, so it's a peak. Index 1 (value 2) is also a valid peak and would be an accepted answer too.
Hints
Approach
Optimal: Binary search on the slope
Intuition
Binary search doesn't need the whole array to be sorted — it only needs a rule that reliably tells you which half a valid answer must be in. Here, comparing nums[mid] with its right neighbor nums[mid + 1] gives exactly that rule.
If nums[mid] < nums[mid + 1], the values are still climbing just after mid. Somewhere further right, that climb has to stop being a climb — either it turns into a peak, or it keeps climbing all the way to the last element, which itself counts as a peak next to the imaginary -infinity past the end. Either way, a peak is guaranteed to exist to the right of mid, so mid itself can be safely ruled out and the search continues in the right half.
If instead nums[mid] >= nums[mid + 1], the values are flat or falling right after mid. By the same logic mirrored, a peak is guaranteed to exist at mid or somewhere to its left, so the search continues in the left half, keeping mid as a candidate.
Each comparison throws away half the array, which is what makes this O(log n) instead of the brute force's O(n).
Steps
- Set
left = 0andright = n - 1. - While
left < right:- Compute
mid = left + (right - left) / 2. - If
nums[mid] < nums[mid + 1], a peak is guaranteed to the right ofmid, so setleft = mid + 1. - Otherwise a peak is guaranteed at
midor to its left, so setright = mid.
- Compute
- When
left == right, that index is a peak — returnleft.
Dry run
nums = [1, 2, 1, 3, 5, 6, 4]
| left | right | mid | nums[mid] | nums[mid+1] | action |
|---|---|---|---|---|---|
| 0 | 6 | 3 | 3 | 5 | 3 < 5 → left = 4 |
| 4 | 6 | 5 | 6 | 4 | 6 >= 4 → right = 5 |
| 4 | 5 | 4 | 5 | 6 | 5 < 6 → left = 5 |
| 5 | 5 | — | loop ends | — | return 5 |
Index 5 (value 6) matches the example's official answer, and it's a peak: 5 on its left and 4 on its right are both smaller.
Edge cases: an array of length 1 skips the loop entirely (left already equals right) and returns index 0. A strictly increasing array keeps moving left right until it lands on the last index, which is correct since the imaginary -infinity past the end makes the last element a peak.
Complexity
Time O(log n) — every comparison between nums[mid] and nums[mid + 1] rules out half of the remaining indices, so the window shrinks to size 1 in about log2(n) steps. This is the bound the problem statement asks for.
Space O(1) — only two pointers and a midpoint are kept, no matter how large the array is.
class Solution:
def findPeakElement(self, nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
if __name__ == "__main__":
print(Solution().findPeakElement([1, 2, 3, 1])) # 2
print(Solution().findPeakElement([1, 2, 1, 3, 5, 6, 4])) # 5Follow-up questions
The nums[mid] < nums[mid + 1] check on its own can no longer tell you which direction guarantees a peak, since a tie gives no slope to follow. You'd need to also compare against the next distinct value, skipping over any run of equal neighbors first, or fall back to a full O(n) scan if long runs of equal values are common.
The same binary-search idea extends to 2D: pick the middle column, find its row maximum, and compare that value against its left and right neighboring columns' values at the same row. Whichever side is bigger is guaranteed to contain a 2D peak, so the search halves the number of columns each step, giving O(rows · log(cols)) instead of the O(rows · cols) a full grid scan would cost.
RecapThe whole problem in a few lines, for the night before
- Spot it: "find a peak / local maximum" in an unsorted array that can zig-zag, with an O(log n) time limit
- Idea: binary search on the slope — if nums[mid] < nums[mid + 1], a peak is guaranteed to the right, otherwise it's at mid or to the left
- Cost: O(log n) time, O(1) space (a full left-to-right scan is O(n))
- Trap: assuming the array must be sorted or shaped like a single hill before binary search can apply — the -infinity boundaries guarantee a peak exists even when the array zig-zags
Frequently asked questions
Binary search only needs a comparison that reliably points toward a valid answer in one half — it never actually required the whole array to be sorted. Comparing nums[mid] to nums[mid + 1] tells you which direction the array is currently sloping, and a slope going up always leads toward a peak somewhere ahead of it, which is enough of a guarantee to safely discard the other half.
Treating the positions just before index 0 and just after the last index as -infinity means the array always starts and ends by "climbing up" from nothing. A sequence that starts low, may go up and down several times, and ends by dropping back to nothing must have at least one local high point somewhere in between — that's the peak the algorithm is guaranteed to find.
It's a good test of whether you can spot a binary-search-shaped decision rule in something that doesn't look like a classic sorted-array search — for example, finding a local maximum in a noisy metric like CPU usage or request latency over time, where you don't need the single global maximum, just a point that's higher than what's immediately around it.
Binary search stops being enough, since it's built to find just one answer quickly by throwing away half the array each time — information about other peaks is lost along the way. Finding every peak needs a single O(n) pass comparing each element with its neighbors, which is the same cost as this problem's brute force approach, because there's no way to skip past a peak without possibly skipping over it.