Contains Duplicate

Hints

1. Name the question being asked. "Does any value repeat?" is a membership test in disguise: as you walk the array, the only thing you need to know about the prefix behind you is the set of values it contained. Not their order, not their positions, not their counts. Recognising that the required state is a set is the whole insight.
2. Start with the honest brute force. Compare every pair: two nested loops, O(n^2) comparisons, O(1) extra memory. Say it out loud, say why it dies (at n = 10^5 that is about 5 x 10^9 comparisons), then improve it. Skipping straight to the optimal answer robs you of the chance to show you can reason about cost.
3. Trade memory for time. A hash set answers "have I seen this?" in O(1) average time. Iterate once; if the current value is already in the set, return true; otherwise insert it. One pass, one set, done.
4. Trade time for memory. If the interviewer forbids extra space, sort the array in place and scan for adjacent equal values. Sorting brings equal values next to each other, so a single linear scan afterwards is enough. This costs O(n log n) and mutates the input, which is a real cost if the caller still needs the original order.
5. Exit as early as the data allows. The set loop returns at the first repeat, so it reads only as far as it must. Any solution that builds a complete structure before comparing sizes gives up that property. Know which one you wrote.
6. Check the degenerate input. A single-element array has no pair to compare, so the loop body never fires and the function must fall through to false. Getting the post-loop return right is the only place this problem has a bug in it.

Solution: three approaches

Approach 1 - Nested loops: O(n^2) time, O(1) space

Compare every element against every later element. Correct, memory-free, and unusable at the stated constraint.

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

Why it is correct: if a duplicate exists at positions i < j, the outer loop eventually reaches i and the inner loop eventually reaches j, so the pair is examined. Why it is slow: the inner loop runs n - 1 times for the first element, n - 2 for the second, and so on, giving n(n - 1)/2 comparisons, which is Theta(n^2). At the upper constraint of 10^5 that is roughly five billion comparisons, several seconds in C and minutes in Python. Worth stating as a baseline, never worth submitting. Its one genuine virtue is that it touches no memory beyond two loop counters, which matters on embedded targets where a heap allocation is a bigger sin than a slow loop. Note also what it does not require: no hashing, so the values need not be hashable, and no ordering, so they need not be comparable. Equality alone is enough. That makes it the only approach here that survives arbitrary opaque objects, and it is the honest answer when an interviewer strips away both the hash function and the comparator. Under those constraints quadratic is optimal, which is a useful reminder that a complexity bound is a statement about the operations you are permitted, not about the problem alone.

Approach 2 - Hash set: O(n) average time, O(n) space

Remember every value you have already read. The set is the entire algorithm.

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

Why it is O(n) and not O(n^2): the loop body runs once per element, and each body performs one hash lookup plus at most one insert. A hash lookup is O(1) on average because the hash function spreads keys across buckets, so the expected chain length stays constant as long as the table resizes to keep the load factor bounded. Multiply n iterations by constant work per iteration and you get O(n). The qualifier "average" is load-bearing: with adversarially chosen keys that all collide, every lookup degrades to a linear scan of one bucket and the whole thing becomes O(n^2). That failure mode is explored in load factor and collisions.

Why it returns early: the check happens before the insert, so the function returns at the first repeated value rather than at the end of the array. On [1, 1, 1, ... ] it reads two elements and stops. This is invisible in the worst-case bound, which assumes all values distinct and forces a full pass, but it halves the expected work on duplicate-heavy inputs.

Why the space is genuinely O(n): in the all-distinct case the set ends up holding every element. For 10^5 Python integers that is a few megabytes, which is fine here and is not fine if the same pattern is applied to a stream of a billion records. When the interviewer follows up with "what if the array does not fit in memory", this is the line they are attacking.

Approach 3 - Sort and scan: O(n log n) time, O(1) extra space

Sorting is a way of buying the same information the set gave you, paid for in time instead of memory.

def contains_duplicate_sorted(nums):
    nums.sort()                      # in place, O(1) auxiliary in CPython
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Why it works: sorting makes equal values adjacent, so a duplicate anywhere in the original array becomes a neighbouring pair after the sort. The scan therefore only needs to compare each element with its immediate predecessor, which is n - 1 comparisons. The cost is dominated by the sort at O(n log n): a comparison sort must distinguish n! orderings and each comparison yields one bit, so log2(n!) = Theta(n log n) comparisons are unavoidable in the general case.

Two costs deserve mention in an interview. First, sort() mutates the caller's array, so if the original order matters you must copy first and the space saving evaporates. Second, "O(1) space" is an approximation: Timsort uses O(n) auxiliary memory in the worst case and merge sort always does, so only an in-place heapsort truly hits O(1). Say "in-place sort, O(1) auxiliary if the library sorts in place" rather than claiming O(1) flatly.

The Python one-liner, and why it is not free

def contains_duplicate_oneliner(nums):
    return len(nums) != len(set(nums))

This is the idiomatic answer and it is perfectly acceptable to write it, provided you can state what it costs. It is O(n) time and O(n) space like approach 2, but it forfeits the early exit: set(nums) consumes the entire iterable before len is called, so on [1, 1, 1, ...] with a hundred thousand elements it does a hundred thousand inserts to learn something the explicit loop learned on element two. It is also unavailable the moment the values are not hashable, or the moment you need to report which value repeated. Use it when brevity is worth more than the early exit, which in an interview is usually never, because the explicit loop is the version that lets you talk.

Complexity comparison

Edge cases to verify

• Single element: [7] -> false. The set loop inserts once and falls through; the sorted scan's range is empty. Both rely on the post-loop return False being present.
• All identical: [4, 4, 4, 4] -> true on the second element. Good input for demonstrating the early exit.
• Duplicate at the very end: [1, 2, 3, 1] -> true only after a full pass. This is the worst case for the set approach even though the answer is true.
• Negative and positive values: [-3, 3] -> false. Hashing handles the sign; a solution that indexes into an array by value would need an offset and would break here.
• Large range, small array: [10^9, -10^9] -> false. Rules out any counting-array approach sized by value range, since that array would need two billion slots.

Where beginners go wrong

• Using a list instead of a set for the membership test. Writing seen = [] and then if n in seen looks almost identical to the correct code and is quadratic: in on a list is a linear scan. The container choice, not the loop, is what makes this algorithm fast. Same bug with a tuple or a string.
• Claiming the one-liner is O(1) space. len(nums) != len(set(nums)) builds a full set before comparing sizes. It is O(n) space, identical to the explicit loop, and it loses the early exit on top. Brevity is not a complexity class.
• Missing the post-loop return. The loop only returns true. If no duplicate exists, control falls off the end, and a function with no explicit return gives back None in Python or a compiler error in Java. This is the single most common actual failure on this problem.
• Inserting before checking. If you write seen.add(n) and then test if n in seen, every element is a duplicate of itself and the function returns true on the first iteration for any non-empty input. The order of the two statements is the algorithm.
• Sorting without asking. nums.sort() mutates the caller's array. If the caller still needs the original order you have introduced a silent bug that no test on the return value will catch. Ask whether the input may be mutated, or sort a copy and stop claiming constant space.
• Reaching for a counting array sized by value range. Values span -10^9 to 10^9, so an index-by-value array would need two billion slots for an array of a hundred thousand elements. Counting sort is the right instinct on a small bounded alphabet and the wrong one here, as counting and radix sort sets out.

Interview follow-ups to expect

• "Return the duplicated value, not just a boolean." Change return True to return n and pick a sentinel for the not-found case. The set already holds everything you need; no structural change.
• "Return every value that appears more than once." A set of seen values plus a set of reported values, so each duplicate is emitted once. Or a Counter and a filter, which costs a full pass but reads better. The frequency counting pattern generalises this.
• "Does any value appear at least three times?" The set is no longer sufficient state; you need counts. This is the cleanest illustration of why "what do I have to remember?" is the question that picks the data structure.
• "The array does not fit in memory." Sort externally and scan, or hash each value into k buckets by hash(v) % k, spill each bucket to disk, and check each bucket independently: equal values always land in the same bucket, so a duplicate can never be split across two of them.
• "There are n + 1 values drawn from 1..n. Find the repeat without extra memory." A different problem wearing the same clothes. The constraint guarantees a cycle in the functional graph i -> nums[i], so Floyd's tortoise and hare finds it in O(n) time and O(1) space. See the mathematics of Floyd's algorithm.
• "Values within k indices of each other only." The sliding window variant: keep a set of the last k values, adding on the right and evicting on the left, so memory drops from O(n) to O(k). Covered under sliding window.

Related reading

• Hash Maps: the module this problem belongs to, including why average-case O(1) is a statement about the hash function rather than the container.
• Why is my hash map slow: what happens when the average case does not arrive, and how to notice.
• Two Sum: the same "remember what you have seen" pass, except the set becomes a map because you now need positions as well as membership.