# Contains Duplicate

- **Canonical ID**: `contains-duplicate`
- **Canonical URL**: https://dsacheatsheet.com/problems/contains-duplicate
- **Difficulty**: easy
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/contains-duplicate/

## 1. Core Invariant / The Trick

Maintain a hash set of previously seen numbers. Return True immediately if the current element is already in the set; otherwise insert and continue.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(N)`
- **Proof**: Single linear pass inserting at most N distinct elements with O(1) expected set operations.

## 3. Minimal Idiomatic Code

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

### TypeScript
```typescript
export function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}
```

### C++
```cpp
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (!seen.insert(x).second) return true;
    }
    return false;
}
```

### Java
```java
boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) if (!seen.add(x)) return true;
    return false;
}
```

### Go
```go
func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))
    for _, x := range nums {
        if _, ok := seen[x]; ok { return true }
        seen[x] = struct{}{}
    }
    return false
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Sorting mutates the input array and takes O(N log N) time; prefer O(N) hash set unless constrained by strict O(1) auxiliary space.

### Follow-ups
- Contains Duplicate II (within distance k): maintain a sliding window set of size <= k.