p10 Contains Duplicate — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

The question is “have I seen this value before?” — that’s a membership question. What data structure answers membership queries in O(1) average?

Hint 2 — Approach menu

Three serious approaches; rank by trade-off:

Pick the one that matches the constraints (LC has loose constraints — pick HashSet).

Hint 3 — Key insight

Walk the array once. Maintain a HashSet of values seen so far. For each new element: if it’s already in the set, return True (early exit). Else add it and continue. If you finish the loop, return False.

Critical: early exit. Don’t materialize the whole set first — that loses the constant-factor advantage on inputs with a duplicate near the start.

Hint 4 — Pseudocode

seen = empty set
for x in nums:
    if x in seen: return True
    add x to seen
return False

That’s it. Three lines of logic.

Hint 5 — Why one-liner is worse + the family of variants

return len(set(nums)) != len(nums) works and is one line, but builds the full set even if a duplicate exists at index 1. For [1, 1, 0, 0, 0, ...] of size 10^6, the explicit loop returns after 2 ops; the one-liner does 10^6.

Loop invariant proof: at the top of iteration i, seen == {nums[0..i-1]} as a set. If nums[i] ∈ seen, then by definition some j < i has nums[j] == nums[i] — a duplicate exists. If after all N iterations no early-exit fired, all N values are distinct.

Time O(N) avg, O(N) worst case (hash collision attacks). Space O(N).

The family — know these as natural extensions:

• LC 219 (within K indices): sliding window of HashSet, size K+1; evict nums[i-K-1] as you advance.
• LC 220 (within K indices AND |val| diff ≤ T): bucket sort — bucket = val // (T+1); collision in same or adjacent bucket = answer.
• LC 287 (find THE one duplicate in [1..N] with N+1 elements, O(1) space): Floyd’s cycle detection on the array as f(i) = nums[i].
• LC 442 (find ALL duplicates, O(1) extra space): in-place marking — negate nums[abs(x) - 1]; if already negative, x is a duplicate.

Massive N (10^11, doesn’t fit RAM): Bloom filter. ~1-2 bytes per element with 1% false positive rate; confirm flagged values via secondary store.