Find Peak Element
Problem
nums where no two adjacent values are equal, return the index of any
peak. Treat the positions outside the array as -∞, so the ends can be
peaks too. Your algorithm must run in O(log n).[1,2,3,1]Output2[1,2,1,3,5,6,4]Output1 or 5[3]Output01 ≤ n ≤ 1000 · -231 ≤ nums[i] ≤ 231-1 · nums[i] ≠ nums[i+1] · Required: O(log n).
Try it yourself
class Solution {
public int findPeakElement(int[] nums) {
}
}
nums[mid] < nums[mid+1] you are walking uphill, and since the far edge is
-∞, a peak must exist to the right. Otherwise one exists at or
left of mid.Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.
Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.
Open the Binary Search guide →Approaches
Brute ForceLinear Scan for First Descent
O(n)Space O(1)Scan left to right and return the first i with
nums[i] > nums[i+1]. We only reach i because
nums[i-1] < nums[i] (or i = 0), so it beats both
neighbours. If the array never descends, the last element is the peak.
public int findPeakElement(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] > nums[i + 1]) return i; // first drop is a peak } return nums.length - 1; // strictly increasing: last is a peak }
Clean and correct, but O(n) fails the O(log n) requirement.
OptimalBinary Search on the Slope
O(log n)Space O(1)Keep the invariant “a peak exists in [left, right]”.
If nums[mid] > nums[mid+1] the slope goes down, so
mid itself may be the peak: right = mid. Otherwise climb:
left = mid + 1. When the window is one cell, that cell is a peak.
public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) right = mid; // downhill: peak at/left of mid else left = mid + 1; // uphill: peak to the right } return left; }
Dry run[1,2,1,3,5,6,4]
- 11l213m564r3 < 5 uphill → l=4
- 212135l6m4r6 > 4 downhill → r=5
- 312135l m6r45 < 6 uphill → l=5
- end121356l r4l == r → peak 5 ✔
Logarithmic, constant space — the intended solution.
left < right, mid + 1 is always in bounds
— no edge checks needed.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Linear Scan for First Descent | O(n) | O(1) |
| Optimal | Binary Search on the Slope | O(log n) | O(1) |
- Thinking binary search needs sorted input — here the slope is the ordering signal.
- Using
right = mid - 1on a downhill step — can skip the actual peak. - Looping with
left ≤ right— thenmid + 1may go out of bounds.
- Justify correctness: climbing toward a
-∞edge must hit a peak. - Clarify that any peak is accepted, not the global maximum.
- Mention the adjacent-distinct guarantee — plateaus would break the argument.