Contains Duplicate

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

1. 1Create an empty hash set named seen, because it must remember every value encountered before the current position.
2. 2Scan each number in nums from left to right, because a value can only be a duplicate of an element that has already been processed.
3. 3Check whether the current number is already in seen before inserting it, because membership proves that this value occurred earlier.
4. 4Return true immediately when the number is found, because one repeated value is enough and continuing the scan cannot change the result.
5. 5Insert a number that was not found, because later elements must be able to detect it as a previous occurrence.
6. 6Return false after the loop, because reaching the end means every number passed the membership check without repeating.

Complexityexpected bounds for hash-set operations

Annotated solutionC++ · one pass with a hash set

#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).

#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.

Common mistakesspecific lines that change the proof