Rust Interview Puzzles: Find the lowest index of a repeating element in a vector
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.