Contains Duplicate

easy array hash set

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Inputnums = [1, 2, 3, 1]

Outputtrue

The value 1 appears at indices 0 and 3.

nums (comma-separated)

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

function containsDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) return true;
        }
        return false;
    }
}

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (!seen.insert(x).second) return true;
    }
    return false;
}

Explanation

We need to know if any number shows up more than once. The slow way is to compare every number against every other number, but the trick here is to remember what we have already seen using a hash set so each check is instant.

A set is a collection that only keeps unique values and can answer "is this already in here?" very quickly. We walk through the array once, and for each value x we ask the set whether it has seen x before.

If x is already in seen, we found a repeat and return True right away. Otherwise we add x to the set and keep going. If we reach the end without any repeat, every value was distinct, so we return False.

Example: nums = [1, 2, 3, 1]. We add 1, then 2, then 3 to the set. When we reach the second 1, it is already in seen, so we return True.

Because each lookup and insert is constant time, we finish in a single sweep through the list.

Time: O(n) Space: O(n)