Contains Duplicate

Problem

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1

Input:  nums = [1, 2, 3, 3]
Output: true

Example 2

Input:  nums = [1, 2, 3, 4]
Output: false

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9

Thinking

• Brute force idea: for each element, scan the rest of the list for the same value → $O(n^2)$. With $n = 10^5$ that is ~$5 \cdot 10^9$ comparisons — too slow.
• Key insight: the question is really “have I seen this value before?”. A set answers that in $O(1)$ average time, so one pass is enough.
• Edge cases to remember: empty list, single element, duplicates at the very end, negative numbers, large values.

Solution

Approach A — my first solution (pop + in)

Pop the first element and check whether it still appears in the remaining list.

Complexity: Time $O(n^2)$ · Space $O(1)$

Why it’s slow — two hidden linear costs per loop:

• nums.pop(0) is $O(n)$: removing the front of a Python list shifts every other element left. (pop() from the end is $O(1)$.)
• temp in nums is $O(n)$: in on a list is a linear scan. (in on a set is $O(1)$.)

It also empties the caller’s list as a side effect.

def has_duplicate_mine(nums: list[int]) -> bool:
    while nums:
        temp = nums.pop(0)  # O(n): shifts the rest of the list
        if temp in nums:    # O(n): linear scan of a list
            return True
    return False

Approach B — sort, then compare neighbours

After sorting, equal values sit next to each other.

Complexity: Time $O(n \log n)$ · Space $O(n)$ for sorted (or $O(1)$ extra with in-place nums.sort(), which mutates the input). Useful when memory is tight.

def has_duplicate_sort(nums: list[int]) -> bool:
    s = sorted(nums)
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            return True
    return False

Approach C — hash set, one pass ✅ best practice

Keep a set of values seen so far; return True the moment one repeats.

Complexity: Time $O(n)$ · Space $O(n)$. Stops early on the first duplicate.

def has_duplicate(nums: list[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Approach D — Pythonic one-liner

A set drops duplicates, so if it’s smaller than the list, something repeated.

Complexity: Time $O(n)$ · Space $O(n)$. Short and fast in practice (the loop runs in C), but it always builds the whole set — no early exit.

def has_duplicate_len(nums: list[int]) -> bool:
    return len(set(nums)) != len(nums)

Scratch / Experiments

Timing on a worst case: no duplicates, so every approach has to look at everything. (Approach A is limited to 10,000 elements — at $10^5$ it would take far longer.)

big = list(range(10_000))
%timeit -n 1 -r 1 has_duplicate_mine(list(big))
%timeit has_duplicate_sort(big)
%timeit has_duplicate(big)
%timeit has_duplicate_len(big)

Takeaways

• Pattern: “have I seen this before?” / uniqueness / counting → hash set (or dict / collections.Counter when you need counts or indices). Trade $O(n)$ memory for $O(1)$ lookups. Fallback when memory matters: sort first, then duplicates are neighbours.
• Mistakes I made:
  • list.pop(0) is $O(n)$ — use collections.deque.popleft() if you really need to pop from the front.
  • x in some_list is $O(n)$; x in some_set is $O(1)$. Pick the container based on the operation.
  • Mutated the input list — avoid side effects unless the problem allows it.
• Related problems: Two Sum (#1, same “seen” idea with a dict), Contains Duplicate II (#219, sliding-window set), Valid Anagram (#242, counting), Longest Consecutive Sequence (#128, set lookups), Find the Duplicate Number (#287, $O(1)$ space twist).