#162 Find Peak Element
frequently reported atMetaSamsungBloombergMicrosoftAmazonGoogle
the problem
In plain words
A peak is strictly greater than its neighbours; imagine nums[−1] = nums[n] = −∞. Adjacent values differ. Return the index of any peak in O(log n).
in nums = [1,2,3,1]
out 2
in nums = [1,2,1,3,5,6,4]
out 1 or 5
Either peak is accepted.
- 1 ≤ n ≤ 1000
- -2³¹ ≤ nums[i] ≤ 2³¹ − 1
- nums[i] ≠ nums[i + 1]
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternModified binary search
If nums[mid] < nums[mid+1] you're walking uphill; keep going right and you must hit a peak before the −∞ edge. Downhill means mid or something left of it is a peak.
solutions
From brute force to optimal
Walk right until the next value is smaller; that index is a peak.
- For i in 0..n−2: if nums[i] > nums[i+1] return i.
- Return n−1.
May walk the whole array.
One index.
class Solution { public int findPeakElement(int[] nums) { for (int i = 0; i + 1 < nums.length; i++) { if (nums[i] > nums[i + 1]) return i; // first time the walk goes downhill } return nums.length - 1; // always uphill: the last element is a peak }}Compare nums[mid] with nums[mid+1] and keep the half that surely contains a peak.
- lo = 0, hi = n−1; while lo < hi.
- Uphill (nums[mid] < nums[mid+1]) → lo = mid + 1.
- Downhill → hi = mid.
- Return lo.
Halves each step.
Three indices.
class Solution { public int findPeakElement(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; // mid < hi, so mid + 1 is always valid if (nums[mid] < nums[mid + 1]) lo = mid + 1; // uphill: a peak exists on the right else hi = mid; // downhill: mid or something left is a peak } return lo; }}Dry run
in the room
How to say it in the interview
talk track
- Lead with the uphill argument — it's the whole proof.
- Note that
mid + 1is always in range because mid < hi in alo < hiloop.
traps
- Using
lo <= hihere: mid can equal n−1 andnums[mid + 1]goes out of bounds.
what they ask next
Follow-ups
Find a Peak Element II (LC 1901), 2D grid?
Binary search on columns: take the max of the middle column, compare with its left/right neighbours, move towards the bigger one. O(m log n).
before you submit
Edge cases to test
- One element: index 0 is a peak.
- Strictly increasing → the last index; strictly decreasing → index 0.
- Integer.MIN_VALUE and MAX_VALUE as values: compare neighbours directly — never add or subtract them.
practise next
Similar problems
- #153Find Minimum in Rotated Sorted ArrayMediumin Binary Search
- #33Search in Rotated Sorted ArrayMediumin Binary Search