Contains Duplicate: The Gateway to Hash-Based Algorithms

LeetCode 217, Contains Duplicate, is often one of the first hurdles you clear when moving from “I know syntax” to “I think algorithmically.” It looks deceptively simple—just determine if any number appears twice in a list. But the way you solve it actually teaches you the most important trade-off in computer science: time vs. space.

This problem is a favorite in interviews at places like Apple and Amazon not because it’s hard, but because it tests whether you can pick the right tool for the job.

Real-World Analogy

Approach 1: Brute Force (Naive)

The most intuitive way to solve this is to just compare everything. Pick the first number, check it against the rest. Pick the second, check it against the rest. Rinse and repeat.

Visualization: Brute Force Comparison

Watch how the number of comparisons explodes even with a tiny array.

Approach 2: Sorting

Here’s a different angle: if we organize the data first, the problem changes. Once the array is sorted, any duplicate values must be neighbors.

This transforms the problem from a global search to a local check. You don’t need to scan the whole list anymore; just check if nums[i] is the same as the guy next to him (nums[i+1]).

Visualization: Sorting Method

Notice how sorting brings the duplicate 2s together, allowing us to spot them in a single pass.

While this is way better than brute force, sorting isn’t free. It modifies your input array (which might annoy your caller) and costs O(n log n) time.

Approach 3: Hash Set (Optimal)

This is the standard “correct” answer in an interview. We use a Hash Set.

Since Sets are designed to enforce uniqueness, they do the heavy lifting for us. We iterate through the array and try to add each number to the Set. The moment we hit a number that’s already in there? Boom, we found our duplicate.

Visualization: Hash Set Detection

See how the algorithm stops immediately upon finding the second 1? We don’t even need to look at the rest of the list.

Implementation

Here is the production-ready code for the Hash Set approach. Notice the early return—we bail out the second a duplicate is found rather than finishing the loop.

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

class Solution {
    public boolean containsDuplicate(int[] nums) {
        // Initialize a HashSet to store unique elements
        Set<Integer> seen = new HashSet<>();
        
        for (int num : nums) {
            // Set.add() returns false if the element is already present
            if (!seen.add(num)) {
                return true;
            }
        }
        
        // If loop finishes, no duplicates were found
        return false;
    }
}

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // Use unordered_set for O(1) average time complexity
        unordered_set<int> seen;
        
        for (int num : nums) {
            // Check if num is already in the set
            if (seen.count(num)) {
                return true;
            }
            // Insert num into the set
            seen.insert(num);
        }
        
        return false;
    }
};

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # Initialize an empty set
        seen = set()
        
        for num in nums:
            # Check if number was already seen
            if num in seen:
                return True
            seen.add(num)
            
        return False
        
    # Alternative One-Liner (Explanation below):
    # return len(nums) != len(set(nums))

Complexity Analysis

Understanding the trade-offs here is crucial for system design (and passing the interview).

Practical Applications

This isn’t just LeetCode trivia; duplicate detection is everywhere in real engineering:

1. Data Validation: Stopping a user from signing up with an email address that’s already in the database.
2. Caching: Checking if a specific request ID has already been handled so you don’t accidentally charge a credit card twice.
3. Fraud Detection: Flagging it when the same IP address tries to make ten transactions in one second.

Common Pitfalls & Edge Cases

• Large Inputs: Always assume $N$ can be up to $10^5$. The brute force solution will fail.
• Negative Numbers: The constraints say numbers can be negative. If you try to get clever and use a simple array as a frequency counter (like arr[num]), your code will crash because arrays can’t have negative indexes. Hash Sets handle this automatically.
• Input Modification: If you choose the sorting approach, ask your interviewer if you’re allowed to mess up the order of the nums array. If not, you have to copy it first, which increases your memory usage anyway.

Conclusion

Contains Duplicate is basically the “Hello World” of Hash-based algorithms. We trade a little bit of memory ($O(n)$ space) for a massive speed boost ($O(n)$ time).

Unless you are working on embedded systems where RAM is incredibly tight, the Hash Set is almost always the way to go. It’s cleaner, faster, and easier to read.