Contains Duplicate
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.
