Back to solutions

Contains Duplicate

EasyArrays

Decide whether any value appears at least twice in the array.

Open problem
Constraints
  • 1 <= n <= 10^5
  • -10^9 <= nums[i] <= 10^9

Hash set membership

Time O(n)Space O(n)

Keep a set of the values you have already seen. Walk the array once: if the current value is already in the set a duplicate exists, otherwise add it. Set lookups are O(1) on average.

Key terms
set:
A collection that stores each value at most once and answers 'is x present?' in average O(1).
membership test:
Checking whether a value already belongs to a collection before inserting it.
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}
Step by step
  1. Create an empty set `seen`.
  2. Iterate over each value x in the array.
  3. If x is already in `seen`, a duplicate is found return true.
  4. Otherwise insert x into `seen` and continue.
  5. If the loop finishes with no repeat, return false.
  6. The driver prints the boolean as the lowercase word true or false.