Skip to main content
← Core interview practiceStep 1 of 7

Contains Duplicate

Easy Subject: Arrays & Hashing
Time Complexity
O(n)
Space Complexity
O(n)

Problem Description

Given a list of integers, determine whether at least one value occurs more than once. Return a Boolean.

Example: [4, 1, 9, 4] returns True; [4, 1, 9] returns False.

Think about: An empty list has no duplicate. Negative numbers need no special handling. What changes if you are allowed to sort the input?

Worked solution Open when you’re ready to compare your approach

Approach

Keep a set of values already seen. Before inserting each value, check whether it is present. Return immediately on the first repeat. If the loop finishes, every value was unique.

def contains_duplicate(nums: list[int]) -> bool:
    seen = set()
    for value in nums:
        if value in seen:
            return True
        seen.add(value)
    return False

The loop visits each element once. Hash set operations are expected constant time, giving O(n) expected time and O(n) space. Sorting can reduce auxiliary space in some settings, but changes the input order and costs O(n log n) time.

Check yourself: Why must the membership test happen before insertion?

Worked trace

For [4, 1, 9, 4], the set starts empty. After the first three values it is {4, 1, 9}. The final 4 is already present, so the answer is True without scanning the rest of the list. For [4, 1, 9], every membership check fails and the loop returns False. The set records values, not positions, because only existence matters here.

Why it works and what to watch for

Before each iteration, seen contains exactly the values in the earlier part of the list. Finding the current value there is therefore equivalent to finding a duplicate. Inserting before checking breaks that invariant: the current value would always appear in the set. An empty list returns False, and negative or very large integers need no special case. A nested-loop comparison uses constant extra space but takes O(n²) time in the worst case. Sorting first can help when memory is constrained, but it changes the input unless you make a copy, and sorting takes O(n log n) time.

Step 1 of 7 · Core interview practice

Put this step into practice.

Solve it before opening the explanation. Compare time and extra space.

Enable JavaScript to save progress. You can still continue through the path.