1. Understanding the Problem

You are given an integer array nums. Your task is to return true if any value appears at least twice in the array, and return false if every element is distinct.

The Core Constraint (The Trap):

Because arrays can contain up to 100,000 elements, checking every number against every other number using nested loops will cause a "Time Limit Exceeded" error. You must find a way to remember what you have seen in the past without sacrificing speed.

2. The Naive Approaches: Brute Force and Sorting

There are two common beginner ways to approach this:

The Brute Force: You use two nested loops. For every number, you scan the rest of the array to see if a match exists.

• Time Complexity: O(N²) — A massive performance bottleneck for large arrays.
• Space Complexity: O(1) — No extra memory is used.

The Sorting Approach: You sort the array first. Once sorted, any duplicates will be sitting right next to each other, so you only need to check adjacent elements.

• Time Complexity: O(N log N) — Better than brute force, but still not the fastest possible time.
• Space Complexity: O(1) or O(N) depending on the language's sorting algorithm.

3. The Optimal Approach: The Hash Set (O(N) Time)

To pass a senior-level technical interview, we want to achieve an O(N) time complexity. We can do this by trading a little bit of memory for a massive boost in speed using a Hash Set.

Imagine you are a bouncer at an exclusive club. Instead of memorizing every person who walks in (or making the line sort themselves alphabetically), you simply carry a clipboard with a guest list. When a person steps up, you check if their name is already on your clipboard. If it is, you caught a duplicate! If it isn't, you write their name down and let them in. Because checking a clipboard takes virtually zero time, you can process the line as fast as people walk up.

A Hash Set works exactly like this clipboard. It allows us to insert and look up numbers in constant O(1) time.

4. The Logic Step-by-Step

1. Initialize the Memory: Create an empty Hash Set called seen to act as your clipboard.
2. Traverse the Array: Create a loop to go through each number in the nums array one by one.
   • The Lookup: Check if the current number is already in your seen set.
   • Early Exit (Duplicate Found): If the number is in the set, it means you have encountered it before. Return true immediately.
   • Update Memory: If the number is not in the set, add it to the seen set and move on to the next number.
3. All Distinct: If the loop finishes and you never triggered the early exit, it means every number was unique. Return false.

5. Complexity Analysis

• Time Complexity: O(N) — We traverse the array exactly once. Hash Set lookups and insertions operate in O(1) average time, giving us an optimal linear runtime.
• Space Complexity: O(N) — In the worst-case scenario (every number is distinct), we will end up storing all N elements inside our Hash Set. We traded space to gain speed.

6. Code Implementations

Expand the sections below to see the optimal O(N) "Hash Set" implementations across different languages.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        
        for num in nums:
            # If the number is already on our clipboard, it's a duplicate
            if num in seen:
                return True
            # Otherwise, add it to the clipboard
            seen.add(num)
            
        # If we checked every number without returning True, no duplicates exist
        return False

        # Note: Python also supports a clever 1-liner:
        # return len(set(nums)) != len(nums)

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

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        
        for (int num : nums) {
            // HashSet.add() returns false if the element is already present
            if (!seen.add(num)) {
                return true;
            }
        }
        
        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) {
            // Check if the number is already in the set
            if (seen.count(num)) {
                return true;
            }
            // Add the number to the set
            seen.insert(num);
        }
        
        return false;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the classic "Contains Duplicate" problem! Understanding how to leverage a Hash Set to reduce O(N²) or O(N log N) time down to O(N) time is one of the most critical realizations in algorithmic problem solving. Recognizing when to spend memory to buy speed is exactly what top-tier engineering managers look for. Keep this "clipboard memory" pattern fresh in your mind—you will use it to solve countless other array and string questions, including the famous Two Sum!