Contains Duplicate

Problem Description

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

Examples

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹

This Problem Is About Membership, Not Comparison

The brute-force reads as: compare every element to every other element. But you’re not comparing magnitudes, you’re answering a membership question: “have I seen this number before?” That’s exactly what a hash set is built for. The moment you reframe the problem as a lookup question, the O(n) solution writes itself.

Solution 1: Brute Force

Check every pair. Two nested loops, O(n²), included here because it demonstrates what the optimal solution is actually replacing.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

#include <vector>

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
            for (int j = i + 1; j < nums.size(); j++)
                if (nums[i] == nums[j]) return true;
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(n²): every pair is checked.
• Space Complexity: O(1): no extra memory.

Where it breaks: 10⁵ elements means up to 5 billion comparisons in the worst case. This doesn’t pass at scale.

Solution 2: Hash Set (One Pass)

Walk through the array. For each element, check if it’s already in the set. If it is, return true. If not, add it and continue. The set gives O(1) average lookup.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // if we've seen this number before, we're done
            if (!seen.add(num)) return true;
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

#include <vector>
#include <unordered_set>

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        std::unordered_set<int> seen;
        for (int num : nums) {
            // insert returns false if the element already existed
            if (!seen.insert(num).second) return true;
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(n): one pass, O(1) average per operation.
• Space Complexity: O(n): worst case the set holds all n elements (all distinct).

Where it breaks: hash collisions in the worst case degrade lookup to O(n), making the algorithm O(n²). This is rare and not a concern in practice, but worth noting if an interviewer pushes on worst-case guarantees.

Why Not Sort First?

Sorting places duplicates next to each other, so you can detect them in a single scan. It’s O(n log n) time and O(1) extra space, which is better than the hash set if memory is constrained. The downside: it modifies the input array. If the problem were “check and then return the original array,” sorting would be off the table. Since this problem only asks for a boolean, sorting is a valid alternative worth mentioning.

Common Mistakes

• Using a list instead of a set for lookups. if num in list is O(n) per check, making the whole thing O(n²). Use a set.
• Sorting and then comparing wrong indices. After sorting, the comparison is nums[i] == nums[i+1], not nums[i] == nums[i-1]. Off-by-one here gives a wrong answer on a single-element array or misses the last pair.
• Returning false too early. A single pair found anywhere means true. Don’t add extra conditions that short-circuit the wrong way.

Frequently Asked Questions

Can you solve this in O(1) space? Yes, by sorting. It changes the array in-place and then scans for adjacent duplicates. O(n log n) time, O(1) space. The trade-off is mutating the input.

What if the array only has one element? A single element can’t duplicate itself, so the answer is always false. Both the hash set approach and the sort approach handle this correctly without special casing.

How is this different from Two Sum? Two Sum needs you to find two specific numbers that sum to a target. This problem just needs to know whether any number appears more than once. The hash set structure is similar, but the lookup condition is different.

← All Problems