Contains Duplicate easy

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 1:

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

Example 2:

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

Steps

1. Create a Set: Utilize a Set data structure to store the unique elements encountered so far. Sets are efficient for checking membership (whether an element already exists).
2. Iterate through the Array: Iterate through the input array nums.
3. Check for Duplicates: For each element in nums, check if it already exists in the Set.
   • If the element is already in the Set, it's a duplicate, so return true.
   • If the element is not in the Set, add it to the Set.
4. No Duplicates Found: If the loop completes without finding any duplicates, return false.

Explanation

The solution leverages the properties of a Set to efficiently detect duplicates. A Set only stores unique values. Attempting to add a value that already exists in the Set has no effect. By checking if an element is already present before adding it, we can quickly identify duplicates. This approach avoids nested loops, leading to a more efficient solution compared to brute-force methods.

Code

function containsDuplicate(nums: number[]): boolean {
    const numSet = new Set<number>(); // Create a Set to store unique numbers

    for (const num of nums) {
        if (numSet.has(num)) { // Check if the number already exists in the Set
            return true; // Duplicate found
        }
        numSet.add(num); // Add the number to the Set
    }

    return false; // No duplicates found
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Set operations (.has() and .add()) are typically O(1) on average.
• Space Complexity: O(n) in the worst case. The Set could potentially store all n elements if there are no duplicates. In the best case (all duplicates), the space complexity is O(1).