LeetCode 217 – Contains Duplicate

Contains Duplicate is a warm-up, and it is on this track for the same reason Length of Last Word is: an easy problem is where an interviewer watches how you decide. There is one line of code and one real decision, and the decision is about space.

The problem

Return true if any value appears at least twice, false if every element is distinct.

[1,2,3,1]            -> true
[1,2,3,4]            -> false
[1,1,1,3,3,4,3,2,4,2]-> true
[1]                  -> false
[]                   -> false

Three answers, and the trade

Approach	Time	Space	Mutates input
Compare every pair	`O(n²)`	`O(1)`	no
Sort, then check neighbours	`O(n log n)`	`O(1)`*	yes
Hash set	`O(n)`	`O(n)`	no

The hash set is the expected answer and the right one by default. The interesting part is that sorting is not simply worse — it uses no extra structure, which matters when the array is enormous and memory is the binding constraint. It is the classic time-for-space trade, and noticing that a warm-up contains one is most of what there is to say.

*Sorting is O(1) extra only if it is in place. Java's Arrays.sort on primitives is; Python's sorted allocates a copy, and list.sort does not.

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {
            // add() returns false if the value was already present -- one lookup, not two.
            if (!seen.add(num)) return true;
        }

        return false;
    }
}

Set.add returning a boolean is the detail worth knowing. The alternative — if (seen.contains(num)) return true; seen.add(num); — hashes the value twice for the same result.

The early return matters more than it looks. On an array whose first two elements match, this touches two values; building the whole set and comparing sizes at the end reads the entire array regardless. Both are O(n); only one stops early.

Python

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        return len(set(nums)) != len(nums)

Correct, idiomatic, and it always reads the whole array — no early exit. If that matters, the explicit loop is the version to write:

    def containsDuplicateEarly(self, nums: list[int]) -> bool:
        seen = set()

        for num in nums:
            if num in seen:
                return True
            seen.add(num)

        return False

Say which you would ship and why. "The one-liner unless the arrays are huge and duplicates are usually early" is a real answer; picking one silently is not.

Complexity

	Time	Space
Hash set	`O(n)` average	`O(n)`
Sort first	`O(n log n)`	`O(1)` in place

Average, because hashing is. Adversarial input can degrade a hash set to O(n) per operation — irrelevant here, and the honest word to use.

Both must read every element in the worst case: a single duplicate could be the last pair, so no correct algorithm inspects fewer than all of them.

The follow-ups this sets up

Contains Duplicate II (219) adds "within k indices of each other", which turns the set into a sliding window. Contains Duplicate III (220) adds a value tolerance as well, which needs an ordered structure rather than a hash set — a genuine step up.

Find the Duplicate Number (287) is the same question with constraints that forbid both extra space and mutation, and the answer is Floyd's cycle detection from problem 142. That progression — set, then window, then ordered set, then cycle detection — is a good hour of preparation, and it starts here.

What the interviewer is checking

That you name the space cost rather than defaulting to a set silently.
That sorting is the O(1)-space alternative, and that it mutates the input.
The early exit, and that the one-liner does not have one.
Set.add's return value, so the value is hashed once.
Empty array and single element.
That hash-set time is an average, not a worst case.