Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Contains Duplicate

Check whether any value appears more than once in an array. Compare the brute force, sorting and hash set solutions and their complexity.

Updated Quick read: 3 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(1)
Sort, then compare neighboursO(n log n)O(n)
Hash setO(n)O(n)

The problem

Given an array of integers, return true if any value appears at least twice, and false if every value is different.

[1, 2, 3, 1]   →  true     (1 appears twice)
[1, 2, 3, 4]   →  false
[]             →  false

Approach 1: brute force

Compare every element with every later element.

JavaScript

function containsDuplicateBruteForce(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Python

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

Time O(n²). Space O(1).

Approach 2: sort, then compare neighbours

After sorting, equal values sit next to each other, so one pass comparing each element with the previous one is enough.

JavaScript

function containsDuplicateSorted(numbers) {
  const sorted = [...numbers].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

Python

def contains_duplicate_sorted(numbers):
    ordered = sorted(numbers)
    for i in range(1, len(ordered)):
        if ordered[i] == ordered[i - 1]:
            return True
    return False

The copy [...numbers] keeps the caller's array unchanged, since sort reorders the array it is called on.

Time O(n log n) for the sort. Space O(n) for the copy.

Approach 3: hash set

Keep a set of the values seen so far. A value that is already in the set is a duplicate.

JavaScript

function containsDuplicate(numbers) {
  const seen = new Set();
  for (const value of numbers) {
    if (seen.has(value)) return true;
    seen.add(value);
  }
  return false;
}

Python

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

This returns as soon as the first duplicate is found, without looking at the rest of the array.

Time O(n). Space O(n).

A shorter version, and its cost

JavaScript

function containsDuplicateShort(numbers) {
  return new Set(numbers).size !== numbers.length;
}

Python

def contains_duplicate_short(numbers):
    return len(set(numbers)) != len(numbers)

A set drops repeated values, so it ends up smaller than the array when there is a duplicate. This has the same O(n) time and space, but it always processes the whole array, even when the first two elements are equal.

Which to choose

The hash set is the usual answer: it is the fastest. Sorting is worth mentioning when memory matters more than time and you are allowed to reorder the input in place, since that avoids the extra set.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(containsDuplicate([1, 2, 3, 1])); // true
console.log(containsDuplicate([1, 2, 3, 4])); // false

Python

print(contains_duplicate([1, 2, 3, 1]))  # True
print(contains_duplicate([1, 2, 3, 4]))  # False

The comment after each line is the result you should see.

Common mistakes

  • Using an array for seen. seen.includes(value) is a loop, which makes the solution O(n²) again.
  • Calling sort() with no comparison function. Numbers are then compared as text. Equal numbers still end up adjacent, so the answer happens to be right here, but the habit causes bugs elsewhere.

Original problem: LeetCode 217: Contains Duplicate