Find Peak Element (LeetCode 162): Binary Search Without a Sorted Array
7 views
A peak element is strictly greater than its neighbors. Given an array where nums[i] != nums[i + 1], return the index of any peak in O(log n) time. Treat positions outside the array as negative infinity. For [1, 2, 3, 1] the answer is 2; for [1, 2, 1, 3, 5, 6, 4] either 1 or 5 is correct.
Why it is a good interview question
Most candidates learn binary search on sorted arrays. This problem asks you to see that binary search really needs only a rule that tells you which half still contains an answer. Explaining that rule clearly matters more than the code.
The linear baseline
Scan once and return the first i where nums[i] > nums[i + 1]. It is O(n) and correct, and it is worth mentioning first so the interviewer knows you have a working answer before you optimize.
The key insight
Look at the middle element and its right neighbor.
- If nums[mid] < nums[mid + 1], you are on an upward slope. Moving right, the values either keep rising until the end (and the last element is a peak, because the outside value is negative infinity) or they drop at some point (and that turning point is a peak). Either way, a peak exists to the right.
- Otherwise nums[mid] > nums[mid + 1], so a peak exists at mid or to its left by the same argument.
def find_peak_element(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo
The loop runs while lo < hi, so mid + 1 is always in range. When the loop ends, lo == hi points at a peak. Time O(log n), space O(1).
Edge cases worth saying
- A single element is a peak.
- A strictly increasing array returns the last index; a strictly decreasing one returns 0.
- If equal neighbors were allowed, the slope argument breaks and the worst case becomes O(n). Mentioning this shows you understand why the constraint exists.
Follow-ups
- Find a peak in a 2D grid (LeetCode 1901): binary search over columns, taking the maximum of each column, for O(m log n).
- Peak index in a mountain array (LeetCode 852): the same code works, with a guaranteed single peak.
- Minimum in a rotated sorted array uses a similar "which half is safe" argument.
How to present it
Give the linear solution, state the slope argument in one or two sentences, write the loop, and trace [1, 2, 1, 3, 5, 6, 4]. If nerves make you mix up lo < hi and lo <= hi, Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly reminding you of details like loop bounds while you explain the idea in your own words.