Contains Duplicate (LeetCode 217) — Hash Set in O(n)

Problem Statement#

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

Examples:

Input:  nums = [1, 2, 3, 1]
Output: true          (the value 1 appears at index 0 and index 3)
 
Input:  nums = [1, 2, 3, 4]
Output: false         (every value is distinct)
 
Input:  nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true          (several values repeat)

Constraints: 1 <= nums.length <= 10^5 and -10^9 <= nums[i] <= 10^9.

The full problem lives on LeetCode 217.

The Short Answer#

Walk the array once, keeping a hash set of the values seen so far. If the current value is already in the set, a duplicate exists — return true immediately. If the loop finishes, every value was distinct — return false. That is O(n) time and O(n) space, and it is the answer an interviewer expects within about a minute.

Why Three Approaches, Not One#

The algorithm is easy. What the question actually measures is whether you can name the trade-off space before you write code — and there are exactly three points on it.

Naming all three, then picking the hash set and saying why, is the signal. Jumping straight to the set without acknowledging the memory cost is a weaker answer, because the follow-up is almost always "now do it in constant space."

Note the middle row's hidden cost: sorting is only O(1) extra space if you are allowed to destroy the caller's array. In Python, nums.sort() mutates in place but sorted(nums) allocates a copy — that distinction is worth stating out loud.

How the Hash Set Sees the Array#

The set is a growing record of everything to the left of the cursor. A duplicate is simply the moment the cursor lands on a value that record already contains.

Dry Run#

nums = [1, 2, 3, 1]

The scan never reaches the end of the array. On a distinct input such as [1, 2, 3, 4] it does, and the function falls through to return false.

Solutions#

Python#

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

Python also allows the one-liner return len(set(nums)) != len(nums). It is correct and idiomatic, but it always builds the whole set before comparing, so it loses the early exit — on an array whose first two elements already collide, the explicit loop returns after two steps while the one-liner still touches all 100,000 elements. Say that out loud if you use it.

JavaScript#

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

Java#

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int value : nums) {
            if (!seen.add(value)) return true;  // add returns false if present
        }
        return false;
    }
}

Java's Set.add returns false when the element was already present, which collapses the check and the insert into one call.

The constant-space alternative#

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()                      # destroys the caller's ordering
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

O(n log n) time, O(1) extra space — but only if mutating the input is allowed. Ask before you reach for it.

The Part Most Answers Skip: Hash Sets Are Not Really O(1)#

"O(1) average" is doing real work in that complexity claim. A hash set lookup is constant time on average, assuming the hash function spreads keys evenly. It is O(n) in the worst case, when every key collides into one bucket.

For this problem that rarely bites, because the inputs are plain integers and both CPython and the JVM hash small integers to themselves, spread across buckets by the table size. But it is not hypothetical in general: crafted inputs that force hash collisions are the basis of hash-flooding denial-of-service attacks, which is why Python has randomised string hashing by default since 3.3.

Two practical consequences worth mentioning:

• The honest complexity is O(n) expected, O(n²) worst case. Saying "O(n) average" shows you know where the bound comes from.
• If the value range is small and known, skip hashing entirely. For values in 0..n, a boolean array or bitset gives true O(1) lookups with no hashing and far better cache behaviour.

def contains_duplicate_bitset(nums: List[int], hi: int) -> bool:
    """Values are known to lie in 0..hi. No hashing, no collisions."""
    seen = bytearray(hi + 1)
    for value in nums:
        if seen[value]:
            return True
        seen[value] = 1
    return False

Common Mistakes#

Using a list instead of a set. if value in seen reads identically whether seen is a list or a set, but on a list it is a linear scan, quietly turning the solution back into O(n²). This is the single most common way this problem is failed.

Returning inside the loop on the negative case. Writing return False in the else branch ends the scan after the first element. False belongs after the loop, not inside it.

Sorting without asking. The sort solution mutates the caller's array. In a real code review that is a bug, not an optimisation.

Claiming O(1) space for sorted(nums). In Python, sorted() allocates a new list — O(n). Only nums.sort() is in place.

The Follow-ups Interviewers Actually Ask#

Contains Duplicate II — duplicates within distance k#

Return true if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k.

The set is no longer "everything seen" but "everything inside a window of size k". Slide the window and evict what falls out of range.

def contains_nearby_duplicate(nums: List[int], k: int) -> bool:
    window = set()
    for i, value in enumerate(nums):
        if i > k:
            window.remove(nums[i - k - 1])   # evict what left the window
        if value in window:
            return True
        window.add(value)
    return False

O(n) time, O(min(n, k)) space. This is LeetCode 219.

Contains Duplicate III — near-duplicate values, not just equal ones#

Return true if there are indices i and j with abs(nums[i] - nums[j]) <= valueDiff and abs(i - j) <= indexDiff.

Equality is gone, so a hash set no longer helps — you need range queries. The standard trick is bucketing: put each value into a bucket of width valueDiff + 1. Two values within valueDiff of each other either share a bucket or sit in adjacent ones, so you only ever check three buckets.

def contains_nearby_almost_duplicate(nums, indexDiff, valueDiff):
    if valueDiff < 0:
        return False
    width = valueDiff + 1
    buckets = {}
 
    for i, value in enumerate(nums):
        key = value // width          # floor division handles negatives correctly
        if key in buckets:
            return True
        for neighbour in (key - 1, key + 1):
            if neighbour in buckets and abs(buckets[neighbour] - value) < width:
                return True
        buckets[key] = value
        if i >= indexDiff:
            del buckets[nums[i - indexDiff] // width]
 
    return False

O(n) time, O(min(n, indexDiff)) space. This is LeetCode 220, and it is a genuine Hard — the jump from "same value" to "nearby value" is the whole difficulty.

What if the data does not fit in memory?#

For a stream too large to hold, exact answers are impossible without O(n) space, so the question becomes probabilistic. A Bloom filter answers "have I seen this?" in constant space per element with a tunable false-positive rate and no false negatives — meaning it may claim a duplicate that is not there, but it will never miss a real one. That asymmetry is usually the right one: flag candidates cheaply, verify the small set exactly.

Key Takeaways#

• The hash set scan is O(n) expected time and O(n) space, and it exits early on the first repeat.
• Name all three approaches — brute force, sort, hash set — before coding; the trade-off is the point of the question.
• Sorting buys O(1) extra space at O(n log n) time, but only if you may mutate the input.
• "O(1) hash lookup" is an average, not a guarantee; the honest worst case is O(n²).
• When the value range is small and known, a bitset beats a hash set on both memory and cache behaviour.
• Contains Duplicate II swaps the set for a sliding window; Contains Duplicate III swaps equality for bucketed range queries and is a genuine Hard.