Contains Duplicate (LeetCode 217)

The problem

You get an array of integers nums. Return True if any value appears at least twice, and False if every element is distinct.

Input:  [1, 2, 3, 1]
Output: True

Input:  [1, 2, 3, 4]
Output: False

In the first array, 1 appears at index 0 and index 3.

How to think about it

Start with brute force. Compare every pair of elements. That is O(n²) time, too slow for 10⁵ elements. A better step: sort, then any duplicates sit next to each other, so one scan of neighbours finds them. That is O(n log n) time, and O(1) extra space if you’re allowed to sort in place.

The key insight: a set remembers what you’ve seen in O(1) per lookup. The question “does anything repeat?” is the most basic hash-set question there is. You could walk the list and stop at the first value already in the set. Or, more simply, build the whole set at once: a set keeps only one copy of each value, so if any value repeated, the set ends up smaller than the list.

Early exit or one-liner? The one-liner always processes the full list. The loop version (if x in seen: return True) can stop as soon as it finds a repeat, which helps on long inputs with an early duplicate. Both are O(n) in the worst case, and either is a fine interview answer if you mention the trade-off.

Which pattern is this? Hash set membership. The tell is “have I seen this value before?”

Approach

1. Build a set from nums. Duplicates collapse into one entry.
2. If the set’s length differs from the list’s length, something was dropped, so return True.
3. Otherwise every value was unique; return False.

Solution

def contains_duplicate(nums):
    return len(set(nums)) != len(nums)   # the set drops repeats, so it shrinks
# contains_duplicate([1,2,3,1]) -> True

Dry run

For the example, the second 1 is dropped when the set is built, so the set has 3 elements against the list’s 4.

Complexity

• Time: O(n). Building the set inserts each element once, at O(1) average per insert.
• Space: O(n). The set can hold every element when they’re all distinct.

Edge cases and pitfalls

• Empty list or one element: no duplicates possible, returns False.
• Negative numbers and zero hash like any other integer; nothing special.
• Space-limited follow-up: if O(1) extra space is required, sort in place and check neighbours, accepting O(n log n) time.
• Large input with an early repeat: the loop-with-early-exit version is faster in practice. Mention it.
• Nearby duplicates (|i − j| ≤ k, LeetCode 219) is a different problem. Store the last index of each value in a dictionary, or keep a sliding window set of size k.

Related problems

• Two Sum (LeetCode 1): the same “have I seen it?” lookup, with the value’s complement.
• Find the Duplicate Number (LeetCode 287): find the repeat in O(1) space without a set.
• Longest Consecutive Sequence (LeetCode 128): another problem where a set is the whole trick.