217. Contains Duplicate

Contains Duplicate is a warm-up, but it’s a clean place to see why “just use a hash set” isn’t always the reflex answer. There are three solutions here, and each trades time against space differently.

Question

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.

• Example1

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

• Example2

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

• Example3

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

• Constraints
  • $1 <= nums.length <= 10^5$
  • $-10^9 <= nums[i] <= 10^9$

Three approaches on one axis

Approach	Time	Extra space
Brute force (all pairs)	$O(n^2)$	$O(1)$
Sort, then scan neighbors	$O(n \log n)$	$O(\log n)$ (Java’s sort stack)
Hash set	$O(n)$	$O(n)$

Answer

/**
 * brute force
 */
public boolean containsDuplicate(int[] nums) {
    if (nums == null || nums.length <= 1) return false;
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

/**
 * Arrays.sort (merge sort) -> O(nlogn)
 * loop -> O(n)
 */
public boolean containsDuplicate(int[] nums) {
    if (nums == null || nums.length <= 1) return false;
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

/**
 * loop -> O(n) 
 */
public boolean containsDuplicate(int[] nums) {
    if (nums == null || nums.length <= 1) return false;
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (set.contains(nums[i])) {
            return true;
        }
        set.add(nums[i]);
    }
    return false;
}

Why the hash set usually wins

It’s the only linear option, and it short-circuits. On [1,2,3,1] it returns the instant it re-sees 1, without touching the rest of the array — it can bail early when a duplicate sits near the front. That’s the same “have I seen this before?” membership question behind Two Sum, answered in expected $O(1)$ per lookup. For most inputs, this is the answer to reach for.

When sorting is the better call

The hash set’s $O(n)$ memory isn’t free, and that’s the trade worth naming out loud in an interview. If the array is huge and memory is tight — or you’re allowed to mutate the input and want to avoid an $O(n)$ hash set — sorting in place and comparing neighbors is $O(n \log n)$ time and only $O(\log n)$ stack space. So the honest rule is “hash set if I can spend the memory, sort if I can’t.” The brute force is only ever a talking point; quadratic time falls apart past a few thousand elements, well inside this problem’s $10^5$ ceiling. The same set-membership idea scales up to trickier problems like Longest Consecutive Sequence, where a hash set turns an apparent sort into a linear scan.

References

• https://leetcode.com/problems/contains-duplicate/