Contains Duplicate — Editorial

Opening the reading…

Intuitionturning repetition into a membership question

A duplicate exists exactly when the current number has appeared somewhere earlier in the scan. Instead of comparing the current number with every earlier element, keep a record of the values you have already seen. Then each new number needs only one question: is it already in that record?

A hash set is designed for this membership check. When a number is missing, insert it so future elements can find it. When a number is already present, the condition is proven immediately and the answer is true. If the scan reaches the end without finding one, every element was distinct, so the answer is false.

Approach

Create an empty hash set named seen, because it must remember every value encountered before the current position.

Scan each number in nums from left to right, because a value can only be a duplicate of an element that has already been processed.

Check whether the current number is already in seen before inserting it, because membership proves that this value occurred earlier.

Return true immediately when the number is found, because one repeated value is enough and continuing the scan cannot change the result.

Insert a number that was not found, because later elements must be able to detect it as a previous occurrence.

Return false after the loop, because reaching the end means every number passed the membership check without repeating.

Complexityexpected bounds for hash-set operations

MEASURE	BOUND	WHY
Time	Expected O(n), worst-case O(n^2)	The loop performs at most one set lookup and one insertion per element, so expected constant-time hash operations give O(n). Severe hash collisions can make individual operations linear, degrading the total to O(n^2). Early termination can make the actual scan shorter.
Space	O(n) extra	The set stores at most one entry for each input value, so it contains no more than n entries. The input array is not copied, and there is no returned collection whose storage needs to be counted.

Here n is the number of elements in nums.

Annotated solutionC++ · one pass with a hash set

CPPScan once, test membership before insertion, and stop at the first duplicate.

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

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

        for (int num : nums) {
            if (seen.count(num)) return true;
            seen.insert(num);
        }

        return false;
    }
};

The order of the two set operations is the key detail. You test first because the set represents values from earlier positions only. Inserting first would make the current value look like something you had already seen, causing every element to appear duplicated. The early return is also part of the intended efficiency: once true is established, the remaining input is irrelevant.

The sorting alternativeless memory, but the scan is no longer linear

Sorting gives a different way to expose duplicates: after sorting, equal values become adjacent. You can then compare each element with the one immediately before it. This is a reasonable choice when modifying nums is acceptable or when reducing auxiliary memory matters, but it costs O(n log n) time instead of the hash set's expected O(n).

CPPSort the values so any duplicate pair becomes adjacent.

#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;
    }
};

This version uses O(1) auxiliary storage aside from the sorting implementation, which commonly uses O(log n) call-stack space for introsort. Its hidden cost is that it rearranges the input array. The hash-set solution preserves the original order and is the better default when the expected linear-time scan is the priority.