4.4.1 — Contains Duplicate

LeetCode 217 · Easy · ★ Blind 75

The problem

Return true if any value in the array appears twice.

[1, 2, 3, 1]  →  true
[1, 2, 3, 4]  →  false

Up to 100,000 numbers, each between -10^9 and 10^9.

The pattern

The question is "have I seen this before?" That question always means a hash set.

The brute force compares every pair, which is O(n^2). The inner loop is really a search: is this value anywhere else in the array? A set answers that in one step instead of n.

The solution

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for n in nums:
            if n in seen:
                return True
            seen.add(n)
        return False

TypeScript

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

Walk the array once. Ask the set if it already holds this value. If it does, you are done. If not, add it and move on.

Check before you insert. If you add first and check second, the first element gets added and then found, so every input reports a duplicate. This ordering comes back in 4.4.3 Two Sum for the same reason: an element must not be allowed to match itself.

Complexity

O(n) time, O(n) space. You spent memory to buy time.

Set lookups are O(1) expected, not guaranteed. If every value hashed to the same bucket, a lookup would degrade to a scan. That only happens with deliberately chosen inputs, and real runtimes randomise their hash seed to stop it (4.3).

The other two answers

Sort, then compare neighbours. O(n \log n) time, O(1) extra space, because sorting puts equal values next to each other. Use it when memory is tight and you are allowed to reorder the caller's array.

len(set(nums)) != len(nums). Correct, but it builds the whole set before comparing anything, so it loses the early exit.

Where this goes next

Same move, one twist added:

• Contains Duplicate II — the two positions must be within k of each other. Keep a sliding set of the last k values.
• Find the Duplicate Number — no extra space allowed at all, which rules out both solutions here and forces cycle detection. Chapter 4.9.
• At scale, when the set will not fit in memory, the answer is a Bloom filter (4.29).

If the values were promised to lie between 1 and n, drop the hash and use a boolean array indexed by value. A bounded small value range turns a hash into an array index — that idea returns in 4.4.5.

Next: 4.4.2 Valid Anagram — same hash, different contents: from "have I seen it" to "how many of each".