All Problems
EasyArrayHash TableSorting

Contains Duplicate

Time Complexity
O(n)
Space Complexity
O(n)

📋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.

💡Examples

1Example 1
Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 appears twice in the array.
2Example 2
Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.
3Example 3
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: Multiple duplicates exist in the array.

⚠️Constraints

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

🧠Approach

There are multiple approaches to solve this problem: 1. **Hash Set (Optimal)**: Use a hash set to track seen elements. - Iterate through the array - For each element, check if it's already in the set - If yes, return true; if no, add it to the set - Time: O(n), Space: O(n) 2. **Sorting**: Sort the array first, then check adjacent elements. - Time: O(n log n), Space: O(1) or O(n) depending on sort 3. **Brute Force**: Compare each element with every other. - Time: O(n²), Space: O(1) - Not recommended The hash set approach is optimal for most cases.

✨Solution

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

// Alternative: One-liner
const containsDuplicate = nums => new Set(nums).size !== nums.length;

🎯Key Points

  • 1Hash Set provides O(1) average lookup time
  • 2Early return when duplicate found improves best-case performance
  • 3One-liner using Set size comparison is elegant but checks all elements
  • 4Sorting approach trades time for space efficiency
  • 5This is a foundational problem for understanding hash tables
Browse More Problems