Contains Duplicate in Rust

Given an integer array, return true when any value appears at least twice. Return false when every value is distinct.

Use a HashSet

A HashSet reports whether an insertion added a new value. If insert returns false, that value was already present.

use std::collections::HashSet;

fn contains_duplicate(nums: &[i32]) -> bool {
    let mut seen = HashSet::with_capacity(nums.len());

    for &value in nums {
        if !seen.insert(value) {
            return true;
        }
    }

    false
}

The expected time complexity is O(n), with O(n) additional space.

Why the early return helps

There is no need to scan the remaining values after finding a duplicate. For an input such as [4, 4, 1, 2, 3], the function stops after the second element.

Compare sorting

Another option is to sort the values and compare adjacent elements:

fn contains_duplicate_sorted(nums: &[i32]) -> bool {
    let mut values = nums.to_vec();
    values.sort_unstable();
    values.windows(2).any(|pair| pair[0] == pair[1])
}

Sorting takes O(n log n) time. This version also clones the input because the function accepts an immutable slice. It can be useful when sorted data is needed for later work.

Test the boundaries

#[test]
fn examples() {
    assert!(contains_duplicate(&[1, 2, 3, 1]));
    assert!(!contains_duplicate(&[1, 2, 3, 4]));
    assert!(!contains_duplicate(&[]));
}