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

 Input `vec` Output `[1, 2, 3, 4, 2]` `true` `[1, 1]` `true` `[1, 2, 3, 4]` `false` `[1]` `false`

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