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

.