LeetCode 217 Solution

Problem 217, Contains Duplicate, asks whether a list contains any repeated number.

At first glance, either hashing or sorting can solve this very simple problem. Neither initial implementation achieved the best practical speed, however, so this post records the optimization process.

1. Hash

A hash-based algorithm has $O(N)$ time and $O(N)$ space complexity. My first version simply used unordered_set.

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    for (int x : nums) {
        // check if the number had appeared before
        if (s.count(x)) return true;
        s.insert(x);
    }
    return false;
}

// Or use the return value of insert directly
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    s.reserve(nums.size());
    
    for (int x : nums) {
        // insert returns pair<iterator, bool>
        if (!s.insert(x).second) {
            return true;
        }
    }
    return false;
}

If we give up early exit and compare only the final result, we can trade a little speed for a flashy one-liner.

bool containDuplicate(vector<int>& nums){
    return unordered_set<int>(nums.begin(),nums.end()).size() < nums.size();
}

Using the standard C++ unordered_set is intuitive, but did not perform especially well. One reason is that its underlying structure commonly uses separate chaining, with two main components:

1. Bucket array: a contiguous region of memory that stores pointers to chains
2. Linked nodes: separately allocated nodes that hold the actual elements and are connected by pointers

Because nodes are dynamically allocated on the heap, they may occupy non-contiguous memory, forcing traversal to jump between locations. Adding elements may also trigger a rehash: allocating a larger bucket array, releasing the old one, and reorganizing the chains. We can make a small improvement by reserving enough space in advance.

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    s.reserve(nums.size());  // Key optimization: reserve enough space up front
    
    for (int x : nums) {
        if (s.count(x)) return true;
        s.insert(x);  // Does not trigger a rehash
    }
    return false;
}

2. Sort

Sort first, then check whether any adjacent elements are equal.

Depending on the sorting method, the theoretical time complexity ranges from $O(N+N)$ to $O(N\log N+N)$, which is worse than hashing. In practice, however, my sorting implementations were faster than the standard unordered container.

The key reason may be that arrays are contiguous in memory, allowing the CPU’s L1/L2 caches to read them efficiently.

bool containsDuplicate(vector<int>& nums) {
    // Use the built-in sort
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 1; ++i) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

After finding sorting more effective, I tried a non-comparison sort, namely radix sort, at the cost of extra space.

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

static const int speedup = []() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return false;

        // Radix sort needs an auxiliary array
        vector<int> buffer(n);
        int* src = nums.data();
        int* dst = buffer.data();

        // Two radix-sort passes for 32-bit integers (16 bits and 65,536 buckets per pass)
        // First pass: process the lower 16 bits
        int count[65536];
        
        // First pass
        // Clear the counters
        for (int i = 0; i < 65536; ++i) count[i] = 0;
        // Count how many numbers belong in each bucket
        for (int i = 0; i < n; ++i) {
            count[(unsigned short)(src[i] ^ 0x80000000)]++; // Flip the sign bit to map signed values correctly
        }
        // Convert counts into indices in dst
        for (int i = 1; i < 65536; ++i) count[i] += count[i - 1];
        // Move the data
        for (int i = n - 1; i >= 0; --i) {
            dst[--count[(unsigned short)(src[i] ^ 0x80000000)]] = src[i];
        }

        // Second pass: process the upper 16 bits
        swap(src, dst);
        for (int i = 0; i < 65536; ++i) count[i] = 0;
        for (int i = 0; i < n; ++i) {
            count[(unsigned int)((unsigned int)(src[i] ^ 0x80000000) >> 16)]++;
        }
        for (int i = 1; i < 65536; ++i) count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; --i) {
            dst[--count[(unsigned int)((unsigned int)(src[i] ^ 0x80000000) >> 16)]] = src[i];
        }

        // Finally, check adjacent elements
        for (int i = 0; i < n - 1; ++i) {
            if (dst[i] == dst[i + 1]) return true;
        }

        return false;
    }
};

This was the fastest version so far, but it still did not match the fastest submissions on the LeetCode leaderboard.

3. Customized HASH

Radix sort processes the data in two stages, each with small initialization and movement loops. Hashing should theoretically need to move the data only once, so I looked for a better hash-table implementation.

The standard unordered container is structured to support later queries, but this problem only needs the insertion step: hashing computes the mapping during insertion, so duplicates can be detected immediately. I therefore tried simple linear probing. Since elements never need to be retrieved later, the usual lookup penalty caused by primary clustering matters less here.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;

        // 1. Trade space for time: make the table size a power of two
        // Keep the load factor below 0.5 to greatly reduce probe collisions
        int hashSize = 1;
        while (hashSize < n * 2) hashSize <<= 1; 
        int mask = hashSize - 1;

        // 2. Use a contiguous array for fast allocation and cache locality
        vector<int> hashTable(hashSize, INT_MIN); 

        for (int x : nums) {
            // 3. Hash with a simple unsigned mapping and bitwise modulo
            unsigned int h = (unsigned int)x;
            int idx = h & mask;

            // 4. Linear probing: if occupied, check the next slot
            while (hashTable[idx] != INT_MIN) {
                if (hashTable[idx] == x) return true; // Duplicate found: exit early
                idx = (idx + 1) & mask; // Move linearly to the next slot
            }
            // 5. Store the new value
            hashTable[idx] = x;
        }

        return false;
    }
};

Several details matter:

• Hash-table size: to keep the load factor below 0.5, allocate more than $2n$ slots. Making hashSize a power of two also enables a cheaper hash-index calculation.
• Hash calculation: linear probing normally requires taking a number modulo hashSize. Modulo involves division and relatively complex hardware, whereas bitwise AND (&) compiles to a simple, inexpensive AND instruction.

Conclusion

In the end, linear probing won.

As an aside, I have almost forgotten some of these data-structure algorithms.