Problem overview
The method findPeakElement(vector<int>& nums) returns the index of any peak. A peak is an element strictly greater than both neighbours. No two adjacent elements are equal, and the positions just outside the array count as negative infinity, so the first element only has to beat its right neighbour and the last only its left neighbour.
For [1, 2, 3, 1] the answer is 2, since 3 is greater than 2 and 1. For [1, 2, 1, 3, 5, 6, 4], both index 1 (the value 2) and index 5 (the value 6) are peaks, and either one is accepted.
The statement asks for O(log n) time and O(1) extra space.
Approach: always climb uphill
A linear scan checks each element against its neighbours and takes O(n) time. It is correct but too slow for this problem. The O(log n) requirement points to binary search, even though the array is not sorted.
The idea works because of a guarantee: if you stand at index i and a neighbour is larger, a peak exists on that side. Walk towards the larger neighbour. The values keep rising until either a peak stops them, or the array ends. At the end of the array, the value outside is negative infinity, so the last element is a peak when the walk reaches it. Since the walk cannot go on rising forever, it ends at a peak.
So at the middle index, compare with the neighbours:
- If the left neighbour is larger (or equal, a case this problem rules out for distinct neighbours), go left.
- Otherwise, if the right neighbour is larger, go right.
- Otherwise neither neighbour is larger, and the middle is a peak.
Each step discards half of the indices, so about log₂ n steps are needed. Trace it on [1, 2, 1, 3, 5, 6, 4] with the window as indices 0 to 6. The middle is 3, holding 3. Its left neighbour 1 is smaller and its right neighbour 5 is larger, so go right: the window becomes 4 to 6. The middle is 5, holding 6. Both neighbours (5 and 4) are smaller, so index 5 is returned.
On [1, 2, 3, 1], the middle of 0 to 3 is index 1, holding 2. The right neighbour 3 is larger, so the window becomes 2 to 3. The middle is index 2, holding 3, and both neighbours are smaller, so the answer is 2.
Step by step
- Set the window.
left = 0andright = nums.size() - 1: a peak can be at any index. - Loop while
left <= right. With<=, a window of one index is still examined, and that index may be the peak. - Take the middle as
left + (right - left) / 2. It equals(left + right) / 2but cannot overflow, because it never adds the two indices. - Ask whether to go left with the helper
canGoLeft(nums, middle). If so, setright = middle - 1. The middle itself is dropped because its left neighbour is larger, so it cannot be a peak. - Otherwise ask whether to go right with
canGoRight(nums, middle), and setleft = middle + 1. - Otherwise return
middle. Neither neighbour is larger, which is the definition of a peak. - Return 0 after the loop. A function returning
intmust not run off its end, which is undefined behaviour. For valid input the loop always returns first. - Write the helpers.
canGoLeftis false at index 0 (nothing to the left) and otherwise returnsnums[i - 1] >= nums[i].canGoRightis false at the last index and otherwise returnsnums[i + 1] >= nums[i].
The solution in C++
class Solution {
public:
bool canGoRight(vector<int> &nums, int i) {
if (i == nums.size() - 1) {
return false;
}
return nums[i + 1] >= nums[i];
}
bool canGoLeft(vector<int> &nums, int i) {
if (i == 0) {
return false;
}
return nums[i - 1] >= nums[i];
}
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (canGoLeft(nums, middle)) {
right = middle - 1;
} else if (canGoRight(nums, middle)) {
left = middle + 1;
} else {
return middle;
}
}
return 0;
}
};
The C++ details:
- Boundary checks come first. Both helpers test the edge index before reading a neighbour. Reading
nums[-1]ornums[nums.size()]is undefined behaviour, and C++ does not stop it. Returningfalseat the edge also encodes the "negative infinity outside the array" rule: the edge has no larger neighbour on that side. - Signed against unsigned.
i == nums.size() - 1compares anintwith asize_t. This is fine for non-negativei. Be careful withnums.size() - 1on an empty vector, which wraps to a huge number. - Reference parameters.
vector<int> &numsavoids copying the vector on each helper call. Copying would make every stepO(n)and destroy theO(log n)bound. - Declaration order. Inside a class, member functions can call each other regardless of the order they appear in, so the helpers could be placed after
findPeakElementas well.
Complexity
Time: O(log n). Every iteration either returns or halves the window. Each helper call is O(1).
Space: O(1). The function uses three integers and no recursion.
Edge cases and common mistakes
- One element.
[5]returns 0: both helpers returnfalse, so the middle is a peak. - Two elements.
[1, 2]returns 1 and[2, 1]returns 0. - Strictly increasing or decreasing.
[1, 2, 3, 4, 5]returns the last index, 4, and[5, 4, 3, 2, 1]returns 0. The negative-infinity rule makes the ends valid peaks. - Assuming the peak is the maximum. Any local peak is accepted. In
[1, 2, 1, 3, 5, 6, 4], index 1 is a valid answer even though 6 is larger. - Using
left < rightin the loop. With this version of the search, which movesrighttomiddle - 1, a window with a single index would be skipped and the function would fall through to the finalreturn 0. - Equal neighbours. The problem guarantees none. If duplicates were allowed, a plateau would break the "climb uphill" argument, and no
O(log n)method could be relied on.
Testing
[1, 2, 3, 1]returns 2.[1, 2, 1, 3, 5, 6, 4]returns 5 (index 1 would also be accepted).[5]returns 0.[1, 2, 3, 4, 5]returns 4.[5, 4, 3, 2, 1]returns 0.
