Contains Duplicate

Examples

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

The value 1 appears twice - once at index 0 and again at index 3.

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

Every number appears exactly once.

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

Several values (1, 3, 4, 2) each repeat.

Constraints

• 1 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

Approach

The most obvious approach is to compare each number against every other number in the list, which works but does a lot of repeated comparisons.

A better idea is to sort the list first - once sorted, any duplicate values end up sitting right next to each other, so a single pass checking neighbors is enough to catch a repeat.

The fastest approach skips sorting altogether: walk through the list once, keeping a hash set of every value seen so far. Before adding a new number, check whether it's already in the set - if it is, you've found your duplicate immediately.

Solutions

Brute Force - Check Every Pair

Compare every number against every number that comes after it. If any pair matches, there's a duplicate. It's simple to reason about, but it looks at every possible pair, so it gets slow as the list grows.

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

Time: O(n²) · Space: O(1)

Better - Sort First

Sort a copy of the list. Once it's sorted, any two equal values are guaranteed to end up next to each other, so a single pass comparing each element to its neighbor is enough to find a duplicate.

function containsDuplicate(nums) {
  const sorted = [...nums].sort((a, b) => a - b);

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) {
      return true;
    }
  }

  return false;
}

Time: O(n log n) · Space: O(n)

Optimal - Hash Set

Walk through the list once. For each number, check whether it's already in a hash set of numbers you've seen so far. If it is, you've found a duplicate immediately; if not, add it and keep going.

function containsDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) {
      return true;
    }
    seen.add(num);
  }

  return false;
}

Time: O(n) · Space: O(n)