# Contains Duplicate

> How to solve Contains Duplicate: detect a repeated array value in one linear pass using a hash set instead of comparing every pair.

- Difficulty: Easy
- Category: Arrays & Hashing
- Topics: Array, Hash Table, Sorting
- Published 2026-08-21

## Problem

You are given an array of integers. Determine whether any value shows up more than once, returning true the moment a repeat exists and false only if every element is distinct.

**Example.** For `[1, 2, 3, 1]` the answer is `true`, since `1` appears at both index `0` and index `3`. For `[1, 2, 3, 4]` the answer is `false`.

## Key idea

Checking every pair of elements against each other answers the question but costs O(n²), and that cost grows fast as the array gets large. Sorting first and then scanning for adjacent equal values gets it down to O(n log n), a solid improvement, but there is a faster route.

Walk the array once, keeping a hash set of every value seen so far. For each new element, check whether it is already in the set before inserting it. If it is, a duplicate has been found and the scan can stop immediately. If the loop finishes without a hit, no duplicates exist. Because a hash set lookup and insert are both average O(1), the whole scan finishes in linear time, trading some memory for speed.

## Solution

```typescript
function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();

  for (const num of nums) {
    if (seen.has(num)) {
      return true; // this value was already recorded on an earlier iteration
    }
    seen.add(num);
  }

  return false;
}
```

## Complexity

- **Time:** O(n). A single pass with constant-time average set operations.
- **Space:** O(n). The set can grow to hold every distinct element in the worst case.

## Watch out for

- Check membership *before* inserting the current value, otherwise every element trivially "finds" itself.
- If memory is constrained, sorting in place and scanning for neighbors gives O(n log n) time with no extra space, a reasonable trade when the hash set's O(n) space is unacceptable.
- Do not confuse this with counting how many duplicates exist: the problem only asks for a yes-or-no answer, so returning early is both correct and faster in practice.

## Pattern

This is the "seen-before" pattern: a hash set that records what has already been visited so a repeat can be recognized in constant time. It is the starting point for a broad family of uniqueness and frequency problems.

---

Canonical URL: https://www.marauderbot.com/questions/contains-duplicate
