Problem overview
A peak element is an element that is greater than both of its neighbours. The method findPeakElement receives an int[] named nums, where no two adjacent values are equal, and returns the index of any peak. The positions just outside the array count as negative infinity, so the first element only has to beat its right neighbour and the last element only has to beat its left neighbour.
In [1, 2, 3, 1] the value 3 at index 2 is the only peak, so the answer is 2. In [1, 2, 1, 3, 5, 6, 4] there are two peaks: 2 at index 1 and 6 at index 5. Either index is accepted. The solution below returns 5.
Because the array is not sorted, a peak can be anywhere, and the array can contain several of them. The task also asks for O(log n) time and O(1) extra space.
Approach: binary search without a sorted array
The obvious way to find a peak element in an array is a linear scan: check every element against its neighbours. That is O(n). To reach O(log n) the search has to throw away half of the indices at every step, which is what binary search does. Binary search is usually taught on sorted arrays, but sortedness is not what makes it work. It works whenever one comparison tells you which half can be discarded.
Here the comparison is between nums[middle] and its neighbours:
- If the left neighbour is larger, walk left from
middle. The values either keep rising as you go left until a peak is reached, or they fall at some point, which also makes a peak. At index 0 the array is bounded by negative infinity, so the walk cannot run out without finding one. A peak is guaranteed on the left side, andmiddleitself is not a peak. - If the right neighbour is larger, the same argument works on the right side.
- If neither neighbour is larger,
middleis a peak and the search is over.
The search window [left, right] keeps one property throughout: the elements just outside it are smaller than the window's edge elements, or the window touches the end of the array. So the largest value inside the window is always a true peak of the whole array, and the window can never become peak-free.
Trace the second example, [1, 2, 1, 3, 5, 6, 4]. The window starts as indices 0 to 6, so middle is 3 and holds 3. The left neighbour is 1 and the right neighbour is 5, which is larger, so the window becomes indices 4 to 6. Now middle is 5 and holds 6. Both neighbours, 5 and 4, are smaller, so the method returns 5.
Step by step
- Declare
leftandrightin oneintdeclaration, as0andnums.length - 1. A peak can be at any index, so the first window covers the whole array. - Loop while
left <= right. The<=matters: when the window shrinks to one index, that index may be the peak and still needs to be examined. - Compute
middleasleft + (right - left) / 2. It gives the same index as(left + right) / 2, but it never adds the two indices together, so it cannot overflowinton a very large array. - Ask a helper,
canGoLeft(nums, middle), whether a peak surely exists on the left. If it does, setright = middle - 1. The middle element is smaller than its left neighbour, so it cannot be a peak and can be dropped. - Otherwise ask
canGoRight(nums, middle). If true, setleft = middle + 1. - Otherwise return
middle. Neither neighbour is larger, which is the definition of a peak. - Return
0after the loop. Java requires a return value on every path. For a valid, non-empty array the loop always returns before this line. - Write the two helpers. Each checks its boundary first:
canGoLeftreturnsfalseat index 0 andcanGoRightreturnsfalseat the last index, because there is nothing on that side. Otherwise each returns a comparison with the neighbour, and a comparison already is aboolean, so noifis needed.
The solution in Java
class Solution {
boolean canGoRight(int[] nums, int i) {
if (i == nums.length - 1) {
return false;
}
return nums[i + 1] >= nums[i];
}
boolean canGoLeft(int[] nums, int i) {
if (i == 0) {
return false;
}
return nums[i - 1] >= nums[i];
}
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 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;
}
};
A few Java details worth noticing:
- The helpers have no access modifier, so they are package-private. That is fine for helper methods used only inside the class.
- Arrays are passed by reference, so handing
numsto a helper copies nothing. The helpers run in constant time and add no memory. - The comparison uses
>=although the neighbours are never equal. With distinct neighbours>=and>give identical answers, so the choice is only a matter of style. - Integer division in
(right - left) / 2rounds down, somiddleis always a valid index inside the window.
Complexity
Every pass through the loop either returns or cuts the window to less than half of its size. An array of length n can be halved only about log n times before the window is empty, so the time is O(log n). The method keeps a handful of int variables and never copies the array, so the extra space is O(1).
Edge cases and common mistakes
- One element.
[7]gives 0. Both helpers returnfalse, because the element has no neighbours, and the method returnsmiddle, which is 0. - Strictly increasing or decreasing arrays.
[1, 2, 3]returns 2, the last index, and[3, 2, 1]returns 0. The ends of the array are peaks whenever the array slopes toward them, which is why the boundary checks returnfalseinstead of going out of range. - Several peaks. Any peak is a correct answer. Do not compare your result to one index only when you test by hand. For
[1, 2, 1, 3, 5, 6, 4], both 1 and 5 are valid. - Reading outside the array. Without the boundary checks,
nums[i - 1]at index 0 throwsArrayIndexOutOfBoundsException. Keeping the checks in the helpers keeps the main loop clean. - Using
left < rightas the loop condition while still movingrighttomiddle - 1. That combination skips the last remaining index and can miss the only peak. - Empty array. There is no valid index to return. The loop never runs and the fallback
return 0is returned, which is not a real index. Keep that in mind if you reuse the method on input that may be empty.
Testing
Try these in the editor above: [1, 2, 3, 1] returns 2; [1, 2, 1, 3, 5, 6, 4] returns 5 (1 is also correct); [1, 2, 3] returns 2; [3, 2, 1] returns 0; [7] returns 0.
