Follow

Follow

# Rust Interview Puzzles: Find the lowest index of a repeating element in a vector

go4fun.fun
·Dec 12, 2022·

### Problem

In a provided vector `vec` we need to find the minimum index of a repeating element.

#### Example 1:

Input: `vec = [6, 7, 4, 5, 4, 7, 5]`
Output: `1`
Explanation: There are several repeating elements in the vector but the element `7` has the lowest index `1`.

#### Example 2:

Input: `vec = [1, 2, 5, 3, 4, 7, 3, 5, 8, 9]`
Output: `2`
Explanation: There are several repeating elements in the vector but the element `5` has the lowest index `2`.

#### Example 3:

Input: `vec = [1, 2, 3, 4, 5, 6]`
Output: `None`
Explanation: There are no repeating elements in the vector.

### Solution

``````fn find_min_index_of_repeating_element_in_vector(vec: &Vec<i32>) -> Option<usize> {
let mut set = HashSet::new();

(0..vec.len())
.rev()
.flat_map(|i| {
let found = if set.contains(&vec[i]) { Some(i) } else { None };
set.insert(vec[i]);
found
})
.last()
}
``````

### Explanation

To solve the puzzle in linear time we can use an auxiliary data structure: `HashSet`. We go backwards over the reversed iterator of the vector indices `i`. When we encounter an element `vec[i]` that is already contained in the `set` (which means the element is repeating), we wrap the index `i` of that element in `Some`, otherwise we return `None` for that iteration. Also, on each iteration we insert the current element `vec[i]` to the `set`. And since we use `flat_map` adapter, it would automatically unwrap found indices from `Some` and would discard `None` results. All transformations up to `last` are lazy and would not trigger any traversal. But the `last` call would trigger the resulting iterator and would traverse it until the index of the last repeating element from the resulting sequence is obtained. That would be the lowest index of the repeating element wrapped in `Some`, or `None` if there are no repeating elements.

### Complexity

The time complexity of this solution is `O(n)` (`n` is a size of the input vector). The auxiliary space complexity is `O(n)` because we used the additional `HashSet` data structure to solve the puzzle.