162. Find Peak Element
Asked at Uber, Bloomberg
Difficulty
Medium
Time
O(log n)
Space
O(1)
Pattern
Array
Companies
2
Problem
You are given an integer array nums. An element is called a peak if it is strictly larger than the element on its left and strictly larger than the element on its right.
Treat the positions just outside the array as if they held negative infinity. So the first element only needs to beat its right neighbor to be a peak, and the last element only needs to beat its left neighbor. This also means a peak always exists.
Return the index of any peak element. If several peaks exist, any one of them is accepted. Your algorithm must run in O(log n) time, so a plain left-to-right scan is not good enough.
A peak beats both sides
Constraints
- ●
1 <= nums.length <= 1000 - ●
-2^31 <= nums[i] <= 2^31 - 1 - ●
nums[i] != nums[i + 1] for all valid i
Examples
nums = [1,2,3,1]2nums = [1,2,1,3,5,6,4]5Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
How to Think About It
Brute force: Linear scan every element, check if it is greater than both neighbors.
Optimized scan: Move in the direction of the larger neighbor to avoid checking every element.
Binary search idea: If mid is less than its right neighbor, the peak lies on the right side.
If mid is less than its left neighbor, the peak lies on the left side; otherwise mid itself is a peak.
Binary search achieves O(log n) by halving the search space each iteration.
Optimal Approach
Use binary search on the array. Compare nums[mid] with nums[mid + 1]. If nums[mid] < nums[mid + 1], the peak must be to the right, so set left = mid + 1. Otherwise, the peak is to the left or at mid itself, so set right = mid. When left equals right, that index is guaranteed to be a peak because at least one peak always exists in such an array.
Binary search on the slope
What Trips People Up in Real Interviews
Clarify whether equal adjacent values are allowed.
Mention that there can be multiple valid answers; returning any one suffices.
Explain why binary search works by arguing monotonic direction toward a peak.
Edge cases: single element array, peak at index 0 or last index.
State the time complexity as O(log n) and space as O(1).
Solution Code
O(log n) timedef findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return leftFrequently Asked Questions
What is the Find Peak Element problem?
A peak element is strictly greater than its neighbors. Given an input array nums where nums[i] != nums[i+1], find a peak element and return its index. You must solve it in O(log n) time.
How do you solve Find Peak Element?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find Peak Element?
Find Peak Element is asked at Uber, Bloomberg. It is a medium difficulty problem.
What are common mistakes on Find Peak Element?
- Clarify whether equal adjacent values are allowed.
- Mention that there can be multiple valid answers; returning any one suffices.
- Explain why binary search works by arguing monotonic direction toward a peak.
- Edge cases: single element array, peak at index 0 or last index.
- State the time complexity as O(log n) and space as O(1).