Contains Duplicate: hash sets vs sorting

A repeated value looks like a small problem. It is also a useful introduction to a larger engineering idea: choosing a data structure around the question you need to ask.

The problem

Given a list of integers, return True if any value appears more than once. Otherwise, return False. This is LeetCode 217, Contains Duplicate.

Input	Result	Why
`[1, 2, 3, 1]`	`True`	The value 1 appears twice.
`[1, 2, 3, 4]`	`False`	Every value is distinct.
`[]`	`False`	There are no repeated values.

Think in membership checks

As you read each number, ask: have I seen this before? A hash set is designed to answer membership questions efficiently. It stores unique values and supports average constant-time lookup and insertion.

Approach 1: keep a set

Time: O(n) expectedSpace: O(n)

def contains_duplicate(nums):
    seen = set()
    for value in nums:
        if value in seen:
            return True
        seen.add(value)
    return False

For [1, 2, 3, 1], the set grows from empty to {1}, then {1, 2}, then {1, 2, 3}. On the final value, 1 in seen is true. We stop immediately.

Each value is visited at most once. With expected constant-time hash operations, total time is O(n). The set can hold all n distinct values, so extra space is O(n). Hash-table performance is an expected bound, not a worst-case guarantee.

An alternative: sort first

After sorting, equal values sit next to each other. Compare adjacent elements and return as soon as a pair matches.

Approach 2: compare sorted neighbors

Time: O(n log n)Space: O(n) worst case in Python

def contains_duplicate_sorted(nums):
    nums.sort()
    for index in range(1, len(nums)):
        if nums[index] == nums[index - 1]:
            return True
    return False

This version changes the input list. Use sorted(nums) if you need to preserve the original order, but remember that it creates a new list.

Python's list sort may use O(n) auxiliary memory. Calling an operation “in place” does not automatically mean it uses O(1) extra space. A different sorting implementation may have different space requirements.

Choose for the constraint

Approach	Expected or worst-case time	Extra space	Changes input?
Hash set	O(n) expected	O(n)	No
Python list sort	O(n log n) worst case	O(n) worst case	Yes

For an unsorted list, the set is usually the clearest direct solution. If the data is already sorted, an adjacent comparison needs only O(n) time and O(1) extra space without another sort.

Try it yourself

Check an empty list, a single element, negative values, a duplicate at the start, and a duplicate at the end. Then change the task: return the first repeated value instead of a boolean.

The next lesson moves from asking whether a value exists to asking how many times it appears.