Problem
For a provided vector of numbers vec
we need to find the peak element. The peak element is an element that is greater or equal to its neighbors. If there are multiple peak elements in the vector, we can return any of them as the solution.
Examples:
Input vec | Output |
[7, 8, 9, 1, 4, 5] | 9 |
[7, 8, 9, 11, 14] | 14 |
[9, 7, 5, 4, 2, 1] | 9 |
[1, 2] | 2 |
[2, 1] | 2 |
[1, 1] | 1 |
[1] | 1 |
Solution
fn find_peak_number(vec: &Vec<i32>) -> i32 {
fn find_peak(v: &Vec<i32>, left: usize, right: usize) -> i32 {
match (left + right) / 2 {
// if mid elem is greater than left and right neighbors, then we found peak elem:
m if (m == 0 || v[m] >= v[m - 1]) && (m == v.len() - 1 || v[m] >= v[m + 1]) => v[m],
// if elem to the left of mid is greater than mid, then search in the left sub-vec:
m if m != 0 && v[m - 1] > v[m] => find_peak(v, left, m - 1),
// otherwise, search in the right sub-vec:
m => find_peak(v, m + 1, right),
}
}
assert!(!vec.is_empty(), "the input vector must not be empty");
find_peak(vec, 0, vec.len() - 1)
}
Explanation
One simple way to solve the puzzle is to use the idea inspired by the Binary search algorithm. Recursively, we find a middle index m = (left + right) / 2
and then there are 3 possible cases to process:
If the element at the middle index
v[m]
is greater than its neighbors (taking into account that there might not be a neighbor to the left or the right ofm
, ifm
is the first or the last element), then we found the peak element.If the element to the left of
m
is greater thanv[m]
, then we recursively search in the left sub-vector:find_peak(v, left, m - 1)
.Otherwise, we recursively search in the right sub-vector:
find_peak(v, m + 1, right)
.
Complexity
The time complexity of the solution is O(log n)
(where n
is the size of the input vector). The auxiliary space complexity is also O(log n)
because we chose to have the recursive binary search implementation, which adds up stack space on every recursive call.