Find Peak Element
Return the index of any element larger than both its neighbours in O(log n): step towards the higher neighbour, because a peak must lie on that side.
Updated Long read: 9 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Binary search towards the higher neighbour | O(log n) | O(1) |
The problem
In an array of integers, a peak is an element that is strictly larger than the element on each side of it. The array is not sorted and may go up and down many times. Two things are promised:
- No two neighbouring elements are equal.
- The positions just outside the array, before the first element and after the last, count as lower than any real value. So the first element is a peak if it beats the second, and the last is a peak if it beats the one before it.
Return the index of a peak. If there are several, any one of them is a correct answer. The solution must run in O(log n) time.
numbers = [1, 4, 8, 5, 2] → 2 (8 is the only peak)
numbers = [4, 9, 6, 3, 7, 12, 10] → 1 or 5 (9 and 12 are both peaks)
numbers = [2, 6, 11] → 2 (the last element)
numbers = [5] → 0 (a single element is a peak)There is always at least one peak: the largest element in the array has nothing bigger beside it.
Approach 1: linear scan
Walk from the left. Because everything before the array counts as lower, the walk begins on a rising slope. The first element whose right-hand neighbour is smaller is therefore a peak: it was reached by climbing, and the next step goes down. If no step ever goes down, the last element is the peak.
JavaScript
function findPeakElementLinear(numbers) {
for (let i = 0; i + 1 < numbers.length; i++) {
if (numbers[i] > numbers[i + 1]) return i;
}
return numbers.length - 1;
}Python
def find_peak_element_linear(numbers):
for i in range(len(numbers) - 1):
if numbers[i] > numbers[i + 1]:
return i
return len(numbers) - 1Time O(n), space O(1). This always returns the leftmost peak. It is correct, but the question asks for O(log n).
Why binary search works on unsorted data
Binary search normally needs sorted data, and this array is not sorted. What it has instead is a guarantee about which half must contain a peak.
Look at the middle element and its right-hand neighbour.
If the neighbour is higher, imagine walking right from that neighbour. Each step either goes up or goes down, since no two neighbours are equal.
- If a step goes down, the element just before that step is a peak: you climbed to reach it, and it is followed by a drop.
- If no step ever goes down, you arrive at the last element still climbing, and the last element is a peak because the position after it counts as lower.
Either way there is a peak somewhere to the right of the middle. The left half can be discarded, even though it may contain peaks of its own.
If the neighbour is lower, mirror the argument. Walk left from the middle: either the ground turns downwards somewhere, giving a peak, or you reach the first element still climbing (when viewed from right to left), and the first element is a peak. The middle itself may be that peak, so it stays in the range.
[4, 9, 6, 3, 7, 12, 10]
^ ^
mid higher neighbour: a peak is guaranteed to the rightThe idea in one line: step towards the higher neighbour, and you can never walk away from every peak.
Approach 2: binary search towards the higher neighbour
JavaScript
function findPeakElement(numbers) {
let lo = 0;
let hi = numbers.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (numbers[mid] < numbers[mid + 1]) {
lo = mid + 1; // uphill to the right: a peak lies beyond mid
} else {
hi = mid; // downhill to the right: a peak is mid or before it
}
}
return lo;
}Python
def find_peak_element(numbers):
lo = 0
hi = len(numbers) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if numbers[mid] < numbers[mid + 1]:
lo = mid + 1 # uphill to the right: a peak lies beyond mid
else:
hi = mid # downhill to the right: a peak is mid or before it
return loThe code is the same as in Peak Index in a Mountain Array. What has changed is the reason it is correct. There, the range always contained the peak. Here, the rule the loop keeps true is weaker but still enough:
The element just left of
lo(if there is one) is lower thannumbers[lo], and the element just right ofhi(if there is one) is lower thannumbers[hi].
In other words, the range lo to hi is always entered uphill from both ends, so it must have a peak inside it. When the range shrinks to one element, that element is higher than both of its neighbours, which is the definition of a peak.
Walkthrough
numbers = [4, 9, 6, 3, 7, 12, 10], which has peaks at index 1 (the 9) and index 5 (the 12):
| lo | hi | mid | numbers[mid] | numbers[mid + 1] | Direction | Action |
|---|---|---|---|---|---|---|
| 0 | 6 | 3 | 3 | 7 | Uphill to the right | lo = 4 |
| 4 | 6 | 5 | 12 | 10 | Downhill to the right | hi = 5 |
| 4 | 5 | 4 | 7 | 12 | Uphill to the right | lo = 5 |
| 5 | 5 | lo equals hi | Return 5 |
The binary search returns 5. The linear scan returns 1 for the same input. Both are right, because both 9 and 12 are larger than their neighbours. The first step threw away the left half along with the peak at index 1, and that was safe: the right half was certain to hold a peak of its own.
Time O(log n): the range halves on every step. Space O(1).
Comparing the approaches
| Linear scan | Binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Which peak it returns | Always the leftmost | Whichever the halving leads to |
| Meets the O(log n) requirement | No | Yes |
| Finds the tallest peak | Not necessarily | Not necessarily |
Neither approach promises the highest peak. Finding the largest value in unsorted data needs a look at every element, so it cannot be done in O(log n).
Checking an answer when several are correct
Because any peak is acceptable, two correct solutions can print different indexes for the same input. That makes "does it print 5?" a poor test. There are two better ones.
The first is to test with inputs that have exactly one peak, so only one answer is possible. The second is to check the property instead of the index: whatever index comes back, is the element there larger than both neighbours? This small helper does that, treating a missing neighbour as lower.
JavaScript
function isPeakAt(numbers, index) {
const leftIsLower = index === 0 || numbers[index - 1] < numbers[index];
const rightIsLower = index === numbers.length - 1 || numbers[index + 1] < numbers[index];
return leftIsLower && rightIsLower;
}Python
def is_peak_at(numbers, index):
left_is_lower = index == 0 or numbers[index - 1] < numbers[index]
right_is_lower = index == len(numbers) - 1 or numbers[index + 1] < numbers[index]
return left_is_lower and right_is_lowerTry it yourself
Copy a solution and the isPeakAt helper from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
The first four inputs have a single peak each, so the index is fixed. The last two lines use the array with two peaks and check the property, which holds for either answer.
JavaScript
console.log(findPeakElement([1, 4, 8, 5, 2])); // 2
console.log(findPeakElement([10, 7, 3])); // 0
console.log(findPeakElement([2, 6, 11])); // 2
console.log(findPeakElement([5])); // 0
console.log(isPeakAt([4, 9, 6, 3, 7, 12, 10], findPeakElement([4, 9, 6, 3, 7, 12, 10]))); // true
console.log(isPeakAt([4, 9, 6, 3, 7, 12, 10], findPeakElementLinear([4, 9, 6, 3, 7, 12, 10]))); // truePython
print(find_peak_element([1, 4, 8, 5, 2])) # 2
print(find_peak_element([10, 7, 3])) # 0
print(find_peak_element([2, 6, 11])) # 2
print(find_peak_element([5])) # 0
print(is_peak_at([4, 9, 6, 3, 7, 12, 10], find_peak_element([4, 9, 6, 3, 7, 12, 10]))) # True
print(is_peak_at([4, 9, 6, 3, 7, 12, 10], find_peak_element_linear([4, 9, 6, 3, 7, 12, 10]))) # TrueThe comment after each line is the result you should see.
Common mistakes
- Believing binary search cannot apply because the array is unsorted. It needs a reason to discard half the range, not sorted data. The higher neighbour provides that reason.
- Checking both neighbours of the middle. Testing
numbers[mid - 1]andnumbers[mid + 1]forces special cases for the first and last index. Comparing with the right-hand neighbour alone is enough, andmid + 1is always in range because the middle is rounded down. - Using
hi = mid - 1. When the right-hand neighbour is lower, the middle may be the peak. It must stay in the range. - Forgetting the edges can be peaks. In
[10, 7, 3]the answer is index 0, and in[2, 6, 11]it is the last index. - Expecting the tallest peak. The function returns a peak. In the walkthrough it happens to be the taller one; with other inputs it will not be.
- Using it when neighbours can be equal. A level step gives no direction, and the guarantee is lost.
The peak finding pattern collects this template with its relatives. For a harder use of the same step, see Find in Mountain Array.
Original problem: LeetCode 162: Find Peak Element