#162
Find Peak Element
Medium Follow the slope
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the index of any element that is strictly greater than its neighbours (outside the array counts as minus infinity), in O(log n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: any element bigger than both neighbours.
Why this works: if you're walking uphill (nums[mid] < nums[mid+1]), a peak must exist ahead; otherwise one exists here or behind.
Example: [1, 2, 3, 1]
mid 1 (2) < 3 → lo 2mid 2 (3) > 1 → hi 2 → peak at 2
✦Hints open one at a time
If nums[mid] < nums[mid + 1], you're going uphill — a peak must exist to the right.
Otherwise a peak exists at mid or to the left.
↗Approach
Binary search on the slope: uphill → lo = mid + 1, downhill → hi = mid. lo ends on a peak.
</>Solution (Java)
class Solution {
public int findPeakElement(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] < nums[mid + 1]) lo = mid + 1; // climb uphill
else hi = mid;
}
return lo;
}
}!Common mistake
Thinking binary search needs a sorted array. It only needs a rule that tells you which half surely contains an answer.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon