# Contains Duplicate

[link](https://leetcode.com/problems/contains-duplicate/) · Easy · `array`, `hash set`, `sorting`

> "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.

## 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.

```python
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.

```python
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.

```python
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.

```python
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.)

```python
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).

---

From https://taosu.blog/notes/0217-contains-duplicate