Rust Interview Puzzles: Check if the vector contains duplicates

Problem

For a provided vector of numbers vec we need to check if it contains any duplicates.

Examples:

Solution 1

fn contains_duplicate_1(vec: &mut Vec<i32>) -> bool {
    vec.sort();
    (1..vec.len()).any(|i| if vec[i] == vec[i - 1] { true } else { false })
}

Solution 2

fn contains_duplicate_2(vec: &Vec<i32>) -> bool {
    let mut set = HashSet::new();
    vec.iter().any(|v| {
        if set.contains(v) {
            true
        } else {
            set.insert(v);
            false
        }
    })
}

Explanation

If we want to solve the puzzle with constant space O(1) (but with O(n*log n) time) without using additional data structures, then we could use Solution 1. The idea here is just to sort the vector vec in-place and then iterate over the vector from the 1st index and check if vec[i] == vec[i - 1]. If that is the case, then we have a duplicate and we return true. We use the function any which is short-circuiting, so it would stop processing and return true as long as the first true is discovered (in other words, when it has found the first duplicate).

Solution 2 could be used if we want to "exchange space for time" i.e. we could have a linear time complexity O(n) (but with O(n) axillary space). For that, we use an auxiliary HashSet to store numbers we have seen already. If we encounter a number v which is already in the set, then we return true. Otherwise, we insert the number v to the set and return false. The function any would return true as soon as the first true is discovered.

Complexity

Solution 1: O(n*log n) time, O(1) auxiliary space\.*

*Actually, sort implementation in rust is adaptive - it does allocate some temporary auxiliary storage, but for short slices a non-allocating insertion sort is used instead. Here we assume that the non-allocating implementation is used.

Solution 2: O(n) time, O(n) auxiliary space for HashSet.

---

Rust Playground with this code