Find Peak Element
Return the index of any element that is larger than both of its neighbors. A lesson in using binary search on an array that is not sorted. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums in which no two neighbors are equal. A peak is an element that is strictly greater than the elements on each side of it. Positions outside the array count as negative infinity, so the first element only has to beat its right neighbor and the last only has to beat its left neighbor.
Return the index of any peak. A peak always exists. If there are several, every one of them is accepted.
Your solution should run in O(log n) time.
Example 1
- Input
- nums = [2, 9, 4]
- Output
- 1
9 is larger than 2 and 4.
Example 2
- Input
- nums = [1, 3, 2, 5, 4]
- Output
- 1 or 3
Both 3 (index 1) and 5 (index 3) beat their neighbors, so either index is correct.
Example 3
- Input
- nums = [8, 6, 3]
- Output
- 0
The first element only needs to beat its one neighbor.
Constraints
- 1 ≤ nums.length ≤ 10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
- nums[i] != nums[i + 1] for every valid i.
Practice
Runs 16 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Find Peak Element in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Find Peak Element
Pattern: Binary search on the slope
The array isn't sorted, but binary search doesn't need sorted data. It needs a test at the midpoint that tells you which half is guaranteed to contain an answer.
Compare nums[mid] with nums[mid + 1]. If the right neighbor is bigger, you're on an uphill slope. Keep walking right and either the values keep rising until the end (and the last element is a peak, because the outside counts as negative infinity) or they fall at some point, and the top of that rise is a peak. Either way, a peak exists to the right of mid. If instead nums[mid] > nums[mid + 1], the same argument going left shows a peak exists at mid or to its left. Each comparison halves the range.
Approach 1: Linear scan
Walk left to right and return the first index i where nums[i] > nums[i + 1], or the last index if you never find one. Since everything before i was rising, nums[i] is a peak. Simple and correct, but O(n).
Time O(n) · Space O(1)
Approach 2: Binary search on the slope
- Set
lo = 0,hi = n - 1. - While
lo < hi, takemid = (lo + hi) // 2. - If
nums[mid] < nums[mid + 1], a peak is to the right:lo = mid + 1. Otherwise one is atmidor left of it:hi = mid. - When
lo == hi, that index is a peak.
Because mid < hi inside the loop, mid + 1 is always in range.
Time O(log n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Binary search on the slope | O(log n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Find Peak Element solution in Python
def find_peak_element(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: a peak is here or to the left
return loFind Peak Element solution in JavaScript
function findPeakElement(nums) {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < nums[mid + 1]) lo = mid + 1; // uphill: a peak is to the right
else hi = mid; // downhill: a peak is here or to the left
}
return lo;
}Common mistakes
- Assuming binary search only works on sorted arrays and settling for the linear scan when O(log n) is required.
- Setting `hi = mid - 1` in the downhill case, which can skip over `mid` when `mid` itself is the peak.
- Comparing with `nums[mid - 1]` and reading index -1 when `mid` is 0.
- Searching for the global maximum. Any local peak is enough, and finding the maximum needs O(n).
What interviewers look for
The thing interviewers want to hear is the justification: "if the right neighbor is higher, going right must eventually hit a peak, because the edge counts as negative infinity." Without that sentence, binary search on an unsorted array looks like a guess.
Use the lo < hi loop with hi = mid and explain why it terminates and why mid + 1 is safe. Then mention that the method finds some peak, not necessarily the highest.
Follow-up questions
What if neighbors could be equal?
Then a flat stretch gives no direction: [1, 1, 1, 2, 1, 1, 1] versus all 1s look the same at the midpoint. In the worst case you have to look at every element, so the lower bound becomes O(n).
How would you find a peak in a 2D grid?
Binary search on columns: find the maximum in the middle column, compare it with its left and right neighbors, and move toward the larger neighbor. That runs in O(rows · log cols).
Can you find the global maximum in O(log n)?
Not in general. The maximum can be any peak, and an adversary can hide it anywhere. It only works when the array has exactly one peak, as in a mountain array.
Companies that ask Find Peak Element
Find Peak Element is tagged by 102 companies in our interview dataset. The score shows how often it comes up at each company.
- BCE96%
- Adevinta95%
- System192%
- Foxconn90%
- Urban Company88.8%
- Check2488%
- Alaska Airlines87%
- Meta85.8%
- Zepto85.7%
- Vinted84%
- Shutterfly84%
- Endava84%
- Evertz84%
- Glance81%
- Just Eat80%
- Coupa Software80%
- Mitre80%
- Ixl Learning79.9%
- C3.ai78%
- Check Point Software Technologies77%
- Telus77%
- Servicetitan77%
- Workspan76%
- Cariad76%
and 78 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required