Follow

Follow

# Rust Interview Puzzles: Find the pivot index in a vector

go4fun.fun
·Dec 13, 2022·

### 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.