Problem overview
A peak is an element greater than its neighbours. The function find_peak_element receives a vector nums in which no two adjacent elements are equal, and returns the index of any peak. The ends count as having a neighbour of negative infinity, so the first element is a peak when it is larger than the second, and the last is a peak when it is larger than the one before it.
For [1, 2, 3, 1] the answer is 2, since 3 beats both neighbours. 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. The vector isn't sorted, but binary search still works, for the reason below.
Approach: always walk uphill
A scan that checks every element is O(n). To do better, notice what the neighbours of the middle element tell you. Take the element at middle:
- If a neighbour is larger, there is a peak on that side. Keep walking in the direction of larger values: either the values keep rising until the end of the vector, where the imaginary negative infinity makes the last element a peak, or they stop rising at some element that is larger than both of its neighbours.
- If neither neighbour is larger,
middleitself is a peak.
So one comparison tells you which half is guaranteed to contain a peak, and the other half can be discarded. Repeating that is a binary search over the indexes, and it needs no sorting.
On [1, 2, 1, 3, 5, 6, 4]: the range is indexes 0 to 6 and the middle is index 3, holding 3. Its left neighbour, 1, is smaller, and its right neighbour, 5, is larger, so the search moves right: indexes 4 to 6. The middle is index 5, holding 6, and both neighbours (5 and 4) are smaller, so the function returns 5.
Step by step
- Record the length in
n. It is ausize, and it is reused for the bounds and the neighbour checks. - Set
leftto0i32. The suffix makes it a signedi32, the type of the result, and subtractions such asmiddle - 1can't underflow the way ausizecould. - Set
rightton as i32 - 1, the last index, because a peak may sit at the very end. - Loop while
left <= right, so the window still holds at least one index. - Compute
middleasleft + (right - left) / 2. - Convert it to
m, ausize, for indexing. - Decide whether to go left.
can_go_leftis true whenm > 0andnums[m - 1] >= nums[m]. The bounds check comes first, and&&stops evaluating when it is false, sonums[m - 1]is never read form = 0. - Decide whether to go right the same way:
m + 1 < nandnums[m + 1] >= nums[m]. - If going left, discard the middle and everything to its right:
right = middle - 1. - Else if going right, set
left = middle + 1. - Otherwise neither neighbour is larger, so
return middle;. - Fall back to
0as the final expression if the loop ever ends without a return.
The solution in Rust
impl Solution {
fn find_peak_element(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut left = 0i32;
let mut right = n as i32 - 1;
while left <= right {
let middle = left + (right - left) / 2;
let m = middle as usize;
let can_go_left = m > 0 && nums[m - 1] >= nums[m];
let can_go_right = m + 1 < n && nums[m + 1] >= nums[m];
if can_go_left {
right = middle - 1;
} else if can_go_right {
left = middle + 1;
} else {
return middle;
}
}
0
}
}
Rust details worth a look:
- Two integer types.
nandmareusize, which Rust requires for indexing and whichlen()returns.left,rightandmiddlearei32, the function's return type. Rust never mixes them in one expression, so the code converts withasin two places. - Short-circuit evaluation. In
m > 0 && nums[m - 1] >= nums[m]the right side runs only if the left side is true. Without that guard,m - 1would underflow form = 0and the index would be out of range. - Out-of-bounds indexing panics. Reading
nums[m + 1]past the end stops the program, which is whym + 1 < ncomes first. - Early return.
return middle;exits from inside the loop; the final bare0is the value of the function when the loop ends normally.
Complexity
Time: O(log n). Every iteration either returns or discards the middle and one side, which is at least half of the window, so there are about log₂ n iterations of constant work.
Space: O(1). A handful of integers are kept.
Edge cases and common mistakes
- One element.
[5]returns 0: both guards are false, so the single element is a peak. - Increasing and decreasing vectors.
[1, 2, 3, 4]returns 3 and[4, 3, 2, 1]returns 0, thanks to the negative-infinity ends. - Two elements.
[1, 3]returns 1 and[3, 1]returns 0. - Several peaks.
[1, 2, 1, 3, 5, 6, 4]returns 5 here, but 1 would be accepted too; don't write a test that expects a specific peak when there are several. - Reading neighbours without a bounds check. This panics at the ends of the vector.
- Comparing with the ends' real neighbours only. Treating the vector's end as a wall, rather than as negative infinity, would hide the peaks at index 0 and the last index.
- Empty vector. The loop doesn't run and the function returns 0, even though no element exists. The problem assumes at least one element.
Testing
[1, 2, 3, 1]gives2.[1, 2, 1, 3, 5, 6, 4]gives5(or1, both are peaks).[5]gives0.[1, 2, 3, 4]gives3.[4, 3, 2, 1]gives0.
