Problem
In a provided vector vec we need to find the pivot index. The pivot index is an index of the pivot element, the element before which all elements are less than the pivot and after which all elements are greater than the pivot.
Example 1:
Input: vec = [5, 3, 4, 6, 2, 7, 10, 8]
Output: 5
Explanation: The element 7 (with the index 5) is the pivot because all elements before 7 are less and all elements after are greater.
Example 2:
Input: vec = [3, 1, 12, 10, 23, 50, 25]
Output: 4
Explanation: The element 23 (with the index 4) is the pivot because all elements before 23 are less and all elements after are greater.
Example 3:
Input: vec = [-4, 1, 25, 50, 8, 10, 23]
Output: 0
Explanation: The element -4 (with the index 0) is the pivot because all elements before -4 are less (the empty sub-vector is assumed to always satisfy) and all elements after are greater.
Example 4:
Input: vec = [3, 2, 1]
Output: None
Explanation: There is no any pivot element in the vector.
Solution
fn find_pivot_index_in_vector(vec: &Vec<i32>) -> Option<usize> {
let mut map = HashMap::new();
//first (reversed) traversal: for each index save to the map current min value
(0..vec.len()).rev().fold(i32::MAX, |min, i| {
map.insert(i, min);
if vec[i] < min {
vec[i]
} else {
min
}
});
//second traversal: find the pivot index
let mut max_left = i32::MIN;
(0..vec.len()).find_map(|i| {
let min_right = map[&i];
let found = if vec[i] > max_left && vec[i] < min_right {
Some(i)
} else {
None
};
if vec[i] > max_left {
max_left = vec[i]
}
found
})
}
Explanation
To solve the puzzle in linear time we use an auxiliary data structure: HashMap.
First, we iterate over the vector vec in the reversed order to find a current minimum element to the right of every index i, and save the index i and the corresponding minimum value to the map. We use fold for that because it allows us to maintain a current min value while we are traversing the vector.
On the second traversal, we go through the vector vec again, but this time from left to right. While doing the traversal, we maintain the current maximum value max_left to the left of every index i. Also we extract a corresponding min_right value (the minimum value to the right of the index i). If the current element vec[i] is greater than the maximum element on the left and less than the minimum element on the right, it means that we have found the pivot element. In that case, we wrap its index in Some, otherwise we return None for that iteration. And since we use find_map function, it would find and unwrap from Some the first pivot we have found, and would return None in case there is no any pivot element.
Complexity
The time complexity of this solution is O(n) (n is a size of the input vector), even though we had to traverse the vector twice. The auxiliary space complexity is O(n) because we used the additional HashMap data structure to solve the puzzle.