Difficulty: Easy · LeetCode 217

Problem

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

Examples

Input

nums: int[]
1 ≤ n ≤ 10⁵, -10⁹ ≤ nums[i] ≤ 10⁹

Output

boolean — true if duplicate exists

Constraints

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

Understanding the problem

Brute force compares every pair — O(n²). Key insight: we only need to know "have I seen this before?" → Hash Set gives O(1) lookup, making one linear pass sufficient.

Intuition

"Have I seen this before?" → Hash Set. Store each number as we go; check the set before inserting. O(1) average lookup replaces O(n) inner scan.

Approach

Initialize empty set seen.
For each num: if num in seen → return True.
Else add num to seen.
End of loop → return False.

Naive Solution — O(n²) Brute Force

Check every pair (i, j) with i < j. Return true on first match.

Python

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

C++

class Solution {
public:
    bool containsDuplicate(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;
    }
};

Java

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;
    }
}

JavaScript

var containsDuplicate = function(nums) {
    for (let i = 0; i < nums.length; i++)
        for (let j = i+1; j < nums.length; j++)
            if (nums[i] === nums[j]) return true;
    return false;
};

Time: O(n²) · Space: O(1)

Optimized Code — Hash Set O(n)

Python

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

C++

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) return true;
            seen.insert(num);
        }
        return false;
    }
};

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums)
            if (!seen.add(num)) return true;
        return false;
    }
}

JavaScript

var containsDuplicate = function(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }
    return false;
};

Time: O(n) · Space: O(n)

Variants

Takeaway

Pattern: Frequency Hashing — "Have I seen this before?" → Hash Set. This is the #1 most common array pattern, foundational to Two Sum, Group Anagrams, Longest Consecutive Sequence, and hundreds more problems.