Contains Duplicate

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.

Example:
Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs at the indices 0 and 3.

Approach: Hash Set

The most efficient way to solve this is to use a Hash Set to keep track of the numbers we’ve seen so far.

1. Initialize an empty Hash Set called seen.
2. Iterate through each number num in the given array nums.
3. For each num, check if it already exists in the seen set.
   • If it does exist, we have found a duplicate! Return true.
   • If it does not exist, add num to the seen set.
4. If the loop finishes without finding any duplicates, return false.

Solution

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

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the array. We iterate through the array exactly once, and Hash Set operations take $O(1)$ time on average.
• Space Complexity: $O(n)$. In the worst case (no duplicates), we store all $n$ elements in the Hash Set.