Problem statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Link to problem

Example 1

Input: nums = [1,2,3,1]
Output: true

Example 2

Input: nums = [1,2,3,4]
Output: false

Example 3

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Solutions

Approach 1: HashSet

A hash set implemented as a HashMap where the value is (), aka just keys, and no values.

Very similar to what we did in Two Sum, we iterate over the array and add elements into a hashset, but if an element already exists in the hashset, we immediately return true.

Implementation in Rust

use std::collections::HashSet;

fn contains_duplicate(numbers: Vec<i32>) -> bool {
    let mut results = HashSet::new();

    for item in numbers {
        if results.contains(&item) {
            return true;
        }
        results.insert(item);
    }
    false
}

Time Complexity: $O(n)$
Space Complexity: $O(n)$
Runtime on LeetCode: $24$ms

You might have noticed that the above implementation would work with any collections construct such as vectors, arrays and hashmaps, it is not just limited to HashSets.

It can be modified to make full use of HashSet because HashSets do not allow duplicates, we could take advantage of this construct by adding all elements into the hashset and comparing the length of hashset and our input array.

Implementation in Rust

fn contains_duplicate(numbers: Vec<i32>) -> bool {
    let resultant_set:HashSet<&i32> = HashSet::from_iter(numbers.iter()); 

    !(&resultant_set.len() == &numbers.len())
}

Runtime on LeetCode: $17$ms

Approach 2: Looping

What one would use if there was a space constraint, this approach has $O(1)$ space complexity but that is overshadowed by it’s $O(n^2)$ time complexity.

Valid approach if you have limited memory but time to spare.

Pseudocode

begin a loop
    select ith element
    begin a loop
        compare ith element with rest of the elements
        if found 
            return true
return false

Implementation in Rust

fn contains_duplicate(numbers: Vec<i32>) -> bool {
    for i in 0..(numbers.len()) {
        for j in 0..(numbers.len()) {
            if i != j {
                if numbers[i] == numbers[j] {
                    return true;
                }
            }
        }
    }
    false
}

Time Complexity: $O(n)$
Runtime on LeetCode: Time Limit Exceeded

Approach 3: Sorting

What happens when you sort a vector? The duplicate elements appear next to each other!
So we first sort the array then look at it for adjacent duplicates.

Implementation in Rust

fn contains_duplicate(numbers: Vec<i32>) -> bool {
    let mut sorted = numbers.clone();
    sorted.sort();

    for i in 0..(sorted.len() - 1) {
        if sorted[i] == sorted[i+1] {
            return true
        }
    }
    false
}

Time Complexity: $O(n logn)$
Space Complexity: $O(n)$
Runtime on LeetCode: $26$ms