Problem overview
The method findPeakElement receives an array nums in which no two neighbours are equal. A peak is an element greater than both of its neighbours, and the positions just outside the array count as minus infinity. So the first element is a peak if it is greater than the second, and the last is a peak if it is greater than the one before it. The method returns the index of any one peak.
For [1, 2, 3, 1] the answer is 2. For [1, 2, 1, 3, 5, 6, 4] both index 1 (the value 2) and index 5 (the value 6) are peaks, and either is accepted. The statement asks for O(log n) time and O(1) extra space.
Approach: always walk uphill
Checking every element is O(n). To do better, notice that the array doesn't have to be sorted for binary search to work. It is enough that, after one comparison, half of the array can be thrown away without losing every answer.
Look at the middle element and its neighbours:
- If the left neighbour is larger, the values go up toward the left. Keep walking left while they keep rising. Either they stop rising at a peak, or they reach index 0, which is a peak because the outside counts as minus infinity. So a peak exists on the left side, and the middle element itself is not one.
- If the right neighbour is larger, the same argument works on the right.
- If neither neighbour is larger, the middle element is a peak.
Each step moves toward a guaranteed peak and halves the search window.
On [1, 2, 1, 3, 5, 6, 4] the window starts as indices 0 to 6. The middle is index 3 (value 3). Its left neighbour 1 is smaller, but its right neighbour 5 is larger, so the window becomes 4 to 6. The middle is now index 5 (value 6), and both neighbours (5 and 4) are smaller, so the method returns 5.
Step by step
- Set the window to every index:
left = 0andright = nums.length - 1, declared in onelet. - Loop while
left <= right. A window of one index can still hold the peak, so the comparison must include equality. - Compute
middleas(left + right) >> 1, the average rounded down. - Ask
this.canGoLeft(nums, middle). The helper reports whether the left side surely holds a peak. - If so, set
right = middle - 1. The middle element has a bigger left neighbour, so it can't be a peak, and it can be dropped. - Otherwise ask
this.canGoRight(nums, middle)in anelse if. - If so, set
left = middle + 1. - Otherwise return
middle. Neither neighbour is larger, so it is a peak. - Return 0 after the loop. The compiler wants a
numberon every path. For a non-empty array the loop always returns first. - Write
canGoLeft. At index 0 there is nothing on the left, so it returnsfalse. - Otherwise it returns
nums[i - 1] >= nums[i]. The comparison is already a boolean. - Write
canGoRightthe same way. At the last index,nums.length - 1, it returnsfalse. - Otherwise it returns
nums[i + 1] >= nums[i].
The solution in TypeScript
class Solution {
canGoRight(nums: number[], i: number): boolean {
if (i == nums.length - 1) {
return false;
}
return nums[i + 1] >= nums[i];
}
canGoLeft(nums: number[], i: number): boolean {
if (i == 0) {
return false;
}
return nums[i - 1] >= nums[i];
}
findPeakElement(nums: number[]): number {
let left = 0, right = nums.length - 1;
while (left <= right) {
let middle = (left + right) >> 1;
if (this.canGoLeft(nums, middle)) {
right = middle - 1;
} else if (this.canGoRight(nums, middle)) {
left = middle + 1;
} else {
return middle;
}
}
return 0;
}
}
The TypeScript details:
- Integer halving with
>>.(3 + 4) / 2is3.5, because anumberis a double. The shift operator converts its operands to 32-bit integers first, then shifts, so(3 + 4) >> 1is3. That is fine for array indices. It would be wrong for values beyond 32 bits:(2 ** 31 + 2 ** 31) >> 1gives0.Math.floor((left + right) / 2)is the safe general form. - Methods are called through
this.canGoLeftandcanGoRightbelong to the class, so a bare call would not find them. - The
>=in the helpers. Neighbours are never equal in this problem, so>=and>behave the same on valid input.>=keeps the search safe if equal neighbours slip in. - The return type
boolean. A comparison already gives a boolean, so noifis needed around it.
Complexity
Time: O(log n). Every iteration discards at least half of the window, and the two helpers take constant time.
Space: O(1). The method keeps a few numbers and makes no recursive calls.
Edge cases and common mistakes
- One element.
[1]returns 0: both helpers returnfalseat their boundaries, so the element itself is the peak. - Two elements.
[1, 2]returns 1 and[2, 1]returns 0. - Strictly increasing or decreasing arrays. The peak is the last or the first element. For
[1, 2, 3, 4, 5]the search keeps moving right and returns 4. - Several peaks. Different correct answers are possible. The method may return a different peak from the one in the statement, as long as it is a real peak.
- Forgetting the boundaries. Reading
nums[-1]in JavaScript doesn't throw. It givesundefined, and comparisons withundefinedarefalse, so the logic can quietly go wrong. The boundary checks make the intent explicit. - Using
right = middle. With theleft <= rightloop this can repeat the same window forever. The code dropsmiddlebecause it is known not to be a peak in those two branches. - Empty array. The loop doesn't run and the method returns 0, although there is no peak to point at. The problem doesn't cover this case.
Testing
nums = [1, 2, 3, 1]gives2.nums = [1, 2, 1, 3, 5, 6, 4]gives5with this code (1 would also be correct).nums = [1]gives0.nums = [1, 2, 3, 4, 5]gives4.nums = [2, 1]gives0.