LeetCode 217: Contains Duplicate in C++: Detect Repeated Values with a Hash Set

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are provided for learning and reference. Other valid approaches may exist. Readers should verify the current requirements on the original LeetCode page.

Article Summary

In this problem, we must determine whether an integer array contains at least one repeated value.

A direct comparison between every pair of numbers would work, but it would be inefficient for large inputs. Instead, we can use a hash set to remember the values we have already processed.

For each number:

1. Check whether it is already in the hash set.
2. If it is, return true.
3. Otherwise, insert it and continue.

This solution demonstrates an important algorithmic pattern: using additional memory to replace repeated searching with fast membership checks.

Original Problem and Credit

This article is based on the LeetCode problem “Contains Duplicate.”

• Original problem: https://leetcode.com/problems/contains-duplicate/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem asks us to determine whether any integer appears more than once in an array.

Original Problem in Simple Terms

We are given an integer array named nums.

We must return:

• true if at least one value appears more than once.
• false if every value appears exactly once.

The array may contain many elements, so repeatedly searching the array for matching values would be unnecessarily expensive.

We need a data structure that can efficiently answer this question:

Have we already processed this value?

A hash set is designed for this type of membership lookup.

Real-World Scenario

Imagine a hypothetical event-processing pipeline.

A service receives a batch of events, and each event has an integer event ID. Under normal conditions, every event ID in the batch should be unique.

However, network retries or message redelivery may cause the same event to appear more than once.

Before processing the batch, the system must determine whether any event ID is duplicated:

• Return true if an event ID has already appeared.
• Return false if every event ID is unique.

For example, consider this batch:

[1, 2, 3, 1]

The event ID 1 appears twice, so the batch contains a duplicate.

This scenario is hypothetical and is used only to explain the original computational problem.

Examples

Example 1: Duplicate Found

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

The value 1 appears at both index 0 and index 3.

In the event-processing scenario, event ID 1 was delivered twice.

Example 2: Every Value Is Unique

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

Every value appears exactly once, so the array does not contain a duplicate.

Example 3: Multiple Duplicates

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

Several values appear more than once.

We only need to find one repeated value to return true.

Mapping to the Original Problem

The hypothetical event-processing scenario maps directly to the original problem.

The scenario changes only the interpretation of the integers. The input type, output type, duplicate rule, and expected results remain unchanged.

Solution Intuition

The main challenge is determining whether the current number appeared earlier in the array.

One possible approach is to compare every number with every number after it. However, this requires many repeated comparisons.

For an array of size n, this pairwise approach can require approximately:

n × (n - 1) / 2

comparisons.

This results in O(n²) time complexity, which is inefficient for large arrays.

Instead, we can keep a record of all the values we have already processed.

Using a Hash Set

A set stores unique values. A hash set additionally provides efficient membership checks.

In C++, unordered_set is a hash-based set:

unordered_set<int> seen;

As we move from left to right through the array:

• seen contains the values from the previously processed positions.
• If the current value is already in seen, it must have appeared earlier.
• Therefore, we have found a duplicate.
• If the current value is not in seen, we insert it and continue.

This approach avoids repeatedly scanning the earlier portion of the array.

Why We Check Before Inserting

The order of operations is important.

For each value, we must:

1. Check whether the value already exists.
2. Insert it only if it does not exist.

Suppose we inserted the current value first:

seen.insert(currentNumber);

If we checked immediately afterward, the current number would always be present in the set.

That would incorrectly report every non-empty array as containing a duplicate.

Therefore, we must check first and insert second.

Algorithm

1. Create an empty hash set named seen.
2. Iterate through every number in nums.
3. For the current number:
   1. Check whether it already exists in seen.
   2. If it exists, return true.
   3. Otherwise, insert it into seen.
4. If the loop finishes without finding a repeated value, return false.

Why the Algorithm Works

We can explain the correctness of the algorithm using an invariant.

Invariant

Before processing nums[i], the hash set seen contains exactly the distinct values from:

nums[0] through nums[i - 1]

Initialization

Before processing the first number, there are no previously processed values.

The hash set is empty, so the invariant is true.

Maintenance

Assume the invariant is true before processing the current number.

There are two possible cases.

Case 1: The Current Number Is Already in the Set

Because seen contains only previously processed values, finding the current number in seen proves that the same value appeared at an earlier index.

Therefore, a duplicate exists, and returning true is correct.

Case 2: The Current Number Is Not in the Set

The current number has not appeared earlier.

We insert it into seen. The set now contains exactly the distinct values processed so far, so the invariant remains true for the next iteration.

Termination

If the algorithm finishes processing the entire array without finding an existing value in seen, no number appeared more than once.

Therefore, every number is unique, and returning false is correct.

Complexity Analysis

Let n be the number of elements in nums.

Time Complexity

We process each of the n numbers at most once.

For every number, we perform:

• One unordered_set lookup.
• At most one unordered_set insertion.

Both operations take average-case O(1) time.

Therefore, the expected time complexity is:

O(n)

The algorithm may return early when it finds a duplicate, but the worst-case expected time complexity remains O(n).

Hash-table operations can theoretically degrade because of excessive hash collisions, but O(n) is the standard expected complexity for this solution.

Space Complexity

In the worst case, every number in the array is unique.

The hash set must then store all n values.

Therefore, the auxiliary space complexity is:

O(n)

Solution: Hash Set

#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;

        for (int currentNumber : nums) {
            if (seen.find(currentNumber) != seen.end()) {
                return true;
            }

            seen.insert(currentNumber);
        }

        return false;
    }
};

Code Explanation

Create the Hash Set

unordered_set<int> seen;

The hash set stores every distinct value that has already been processed.

We use a set instead of a map because we only need to know whether a value exists. We do not need to associate each number with another value.

Process Each Number

for (int currentNumber : nums) {

This range-based loop visits every number in the input array.

The variable currentNumber represents the value currently being processed.

Check for an Earlier Occurrence

if (seen.find(currentNumber) != seen.end()) {
    return true;
}

The find() function searches for currentNumber inside the hash set.

• If the value exists, find() returns an iterator pointing to that value.
• If the value does not exist, it returns seen.end().

Therefore, the condition means that the current number has already appeared.

Once a duplicate is found, the function immediately returns true. There is no need to process the remaining values.

Store a New Value

seen.insert(currentNumber);

If the current number has not appeared before, we insert it into the hash set.

This allows future iterations to detect another occurrence of the same value.

Return false

return false;

If the loop finishes, no value appeared more than once.

Therefore, the array does not contain a duplicate.

Walkthrough

Consider the following input:

nums = [1, 2, 3, 1]

The hash set starts empty:

seen = {}

Process 1 at Index 0

Check whether 1 exists in the set:

No

Insert 1:

seen = {1}

Process 2 at Index 1

Check whether 2 exists in the set:

No

Insert 2:

seen = {1, 2}

Process 3 at Index 2

Check whether 3 exists in the set:

No

Insert 3:

seen = {1, 2, 3}

Process 1 at Index 3

Check whether 1 exists in the set:

Yes

The earlier 1 came from index 0, so the current 1 is a duplicate.

The function returns:

true

The complete process is:

Alternative Approach: Sorting

Another solution is to sort the array and compare adjacent values.

After sorting, duplicate values will appear next to each other.

For example:

[3, 1, 2, 1]

becomes:

[1, 1, 2, 3]

The first two values are equal, so a duplicate exists.

A sorting-based solution would look like this:

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }

        return false;
    }
};

The sorting approach has:

Time Complexity: O(n log n)

Its auxiliary space usage depends on the sorting implementation.

This approach also changes the order of the input array. The hash-set solution is preferable when we want expected O(n) time and are allowed to use O(n) additional memory.

Common Mistakes

Inserting Before Checking

The following order is incorrect:

seen.insert(currentNumber);

if (seen.find(currentNumber) != seen.end()) {
    return true;
}

After insertion, the current number will always exist in the set.

The correct order is:

if (seen.find(currentNumber) != seen.end()) {
    return true;
}

seen.insert(currentNumber);

Comparing Every Pair

A nested-loop solution is logically correct, but it has O(n²) time complexity.

For large arrays, this performs far more comparisons than necessary.

Using a Hash Map When Only Membership Matters

A hash map stores key-value pairs.

This problem does not require a count or any additional information for each number. We only need to determine whether the number has already appeared.

Therefore, a hash set is sufficient.

Forgetting the Final Return

If the loop finishes without finding a duplicate, the function must return:

return false;

Returning the Duplicate Value

This problem asks only whether a duplicate exists.

It does not ask us to:

• Return the duplicated number.
• Count repeated values.
• Find every duplicate.
• Return the index of a duplicate.

The required output is a boolean value.

Key Takeaways

1. A hash set is useful when a problem asks whether an item has already appeared.
2. C++ provides the unordered_set container for average-case O(1) membership checks and insertions.
3. Checking before inserting prevents the current value from matching itself.
4. Returning immediately after finding a duplicate avoids unnecessary processing.
5. Using O(n) additional memory reduces the expected running time from O(n²) to O(n).