Contains Duplicate

Given an integer array, return True if any value appears at least twice.

TimeO(n)

SpaceO(n)

Given an integer array nums, return True if any value appears at least twice, and False if every element is distinct.

Constraints

Input: one line of space-separated integers (read from stdin with split_whitespace()).
Output: print True or False on one line.
Answer rule: return True as soon as any duplicate value is found.
Empty / single element: an array with 0 or 1 element has no duplicate → False.

Input

1 2 3 1

Output

True

Explanation: 1 appears at indices 0 and 3 — a duplicate exists.

Naive Solution

Compare every unordered pair (i, j) where i < j. If nums[i] == nums[j], return True.

Two nested loops — no extra storage, but every pair may be checked.

// Compare every unordered pair (i, j) where i < j.
// Time: O(n²)  Space: O(1)
fn contains_duplicate_naive(numbers: &[i64]) -> bool {
    let numbers_length: usize = numbers.len();
    for f_idx in 0..numbers_length {
        for s_idx in (f_idx + 1)..numbers_length {
            if numbers[f_idx] == numbers[s_idx] {
                return true;
            }
        }
    }
    false
}

Time — O(n²)

The inner loop runs (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons → O(n²).

Space — O(1)

Only two index variables — no auxiliary collection.

Time: for n = 1,000, roughly 500,000 pair checks. Most comparisons are wasted once you know a duplicate exists.

Space: essentially free at O(1), but time is quadratic.

Next step: sort the array so equal values sit next to each other, then only compare neighbors.

Two-Pass Solution

Sort the array in ascending order, then scan adjacent pairs. If sorted[i] == sorted[i + 1], a duplicate exists → return True.

If the scan finishes with no match, return False.

Sorting groups equal values together — duplicates become neighbors.

// Sort ascending; duplicates become adjacent neighbors.
// Time: O(n log n)  Space: O(n)
fn contains_duplicate_sort(numbers: &[i64]) -> bool {
    let mut sorted_numbers: Vec<i64> = numbers.to_vec();
    sorted_numbers.sort();
    for idx in 0..sorted_numbers.len().saturating_sub(1) {
        if sorted_numbers[idx] == sorted_numbers[idx + 1] {
            return true;
        }
    }
    false
}

Time — O(n log n)

Sorting dominates; the neighbor scan is O(n).

Space — O(n)

sorted() / to_vec() allocates a copy of length n.

Tradeoff: better than O(n²), but still copies and sorts the whole array. Can we detect repeats in one pass?

Optimal Solution

Walk the array once with a hash map (or set). For each num:

If num is already in the map → return True.
Otherwise insert num.

If the loop finishes, return False.

// Single pass: return true on first repeat seen.
// Time: O(n)  Space: O(n)
fn contains_duplicate_hash_map(numbers: &[i64]) -> bool {
    let mut frequency_counter: HashMap<i64, u8> = HashMap::new();
    for &num in numbers {
        if frequency_counter.contains_key(&num) {
            return true;
        }
        frequency_counter.insert(num, 1);
    }
    false
}

Time — O(n)

Single pass; each map lookup and insert is O(1) average → O(n) total.

Space — O(n)

The map stores up to n distinct values before a duplicate is found.

Result: same correctness as brute force and sort, with O(n) time and early exit on the first repeat.

Full source: Rust · Python