Contains Duplicate, taught start to finish

Easy · target 10 minutes · practise it: search “contains duplicate” on LeetCode (problem 217), HackerRank or Codility. Not affiliated with any of them.

The problem

You are handing out raffle tickets at a school fair, and each ticket should carry a different number. At the end of the day you have the list of numbers you wrote down. Did you write any number twice?

You get a list of whole numbers nums. Return True if some value appears at least twice, and False if every value is different.

Clarify first

• Can the list be empty? (Yes. Then nothing repeats, so the answer is False.)
• Do they want which number repeats? (No, only whether one does. So we can stop at the first repeat.)
• May I change the list, for example by sorting it? (Ask. If not, sort a copy.)

Brute force: compare every pair

• Take the first number and compare it with every number after it. Then take the second, and so on.
• With n numbers that is about n²/2 comparisons. Fine for a few hundred tickets; 10⁵ tickets means 5 × 10⁹ checks.

def contains_duplicate_brute(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

Better: sort, then look at neighbours

Sort the numbers and equal values end up side by side. One walk along the neighbours then finds a repeat.

def contains_duplicate_sorted(nums: list[int]) -> bool:
    nums = sorted(nums)  # a copy, so the caller's list is untouched
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:  # equal values sit side by side now
            return True
    return False

Sorting the list itself with nums.sort() saves the copy, but Python’s sort still borrows scratch memory for up to n/2 items, so the extra space stays O(n). And sorting does far more than we asked for. We do not need the numbers in order; we only need to recognise one we have met before. What remembers things instantly?

Optimised: a set of the numbers we have seen

• Walk the list once and keep a set: a bag of values that answers “is this in here?” in one step, on average, however big it gets.
• For each number, ask the set first. If the number is there, we have found a repeat. If not, drop it in and move on.
• We stop at the first repeat, so [5, 5, …] is answered after two steps.

1. seen = empty set
2. for each number x in nums:
3.     if x is in seen: return True
4.     add x to seen
5. return False

def contains_duplicate(nums: list[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True  # stop at the first repeat
        seen.add(x)
    return False

A one-line version: len(set(nums)) < len(nums). Same O(n), but it always reads the whole list and builds the whole set, even when the repeat is at the front.

Why it works

• At every step, seen holds exactly the numbers before the current one. So “x is in seen” means “x appeared earlier”, which is a repeat.
• If a value appears twice, its second copy is checked after the first copy went into the set, so the repeat is always caught.
• The loop visits each number once and either returns early or reaches the end, where no repeat exists, so False is correct.

Dry run: nums = [14, 3, 9, 27, 3]

Complexity

Edge cases

• Empty list or one number: nothing can repeat → False. ✓
• Negative numbers and zero: a set treats them like any other value. ✓
• The repeat is the first and last number: found on the final step. ✓
• Every number the same: found on the second step. ✓

Common mistakes

• Writing if x in nums[:i]. in on a list checks items one by one, so the “single pass” is secretly O(n²).
• Sorting the caller’s list in place when you were told not to change the input.
• Returning the repeated number (or 1) when a True/False answer was asked for.

Variations

• Contains Duplicate II (LeetCode 219): a repeat no more than k positions apart → keep a set of only the last k numbers (a sliding window).
• Find the Duplicate Number (LeetCode 287): no extra memory and no changes allowed → fast and slow pointers.
• Find All Duplicates in an Array (LeetCode 442): values from 1 to n → mark each value’s home position instead of using a set (the cyclic-sort family).

Interview takeaways

• This is the smallest “have I seen it?” problem. Give all three ideas with their costs: pairs O(n²), sort O(n log n), set O(n).
• A likely follow-up: “memory is tight”. Sorting the list itself avoids the set’s n entries, though Python’s sort still needs up to n/2 scratch slots; only a hand-written sort such as heapsort works in O(1) extra space.
• The same seen-set shape returns in Happy Number (LeetCode 202) and Longest Consecutive Sequence (LeetCode 128).