Frontend Beauty
ESC

Type to search the knowledge base.

Contains Duplicate

Detect any duplicate in an array — Set vs sort, O(n) hash, and follow-ups like nearby duplicates (k-window).

beginner3 min read
  • dsa
  • arrays
  • interview
  • Google
  • Meta

The problem

Return true if any value appears at least twice in nums, else false.

[1, 2, 3, 1] → true
[1, 2, 3, 4] → false

Warm-up for hash sets. Same pattern as “has this id already been seen in this session?”

Brute force

function containsDuplicateBrute(nums: number[]): boolean {
  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)

Sort approach

function containsDuplicateSort(nums: number[]): boolean {
  const a = [...nums].sort((x, y) => x - y);
  for (let i = 1; i < a.length; i++) {
    if (a[i] === a[i - 1]) return true;
  }
  return false;
}
Time O(n log n)
Space O(n) copy or O(1) if mutating allowed

Optimal: Set

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;
}

// or one-liner (no early exit on large unique prefix + dupe at end same asymp)
function containsDuplicateOneLiner(nums: number[]): boolean {
  return new Set(nums).size !== nums.length;
}
Time O(n) average
Space O(n)

Early-exit version is better when a duplicate appears early.

Edge cases

  • Empty / single element → false
  • All same → true
  • Negatives and zeros
  • Very large n — space tradeoff vs sort

Follow-ups

  1. Contains Duplicate II — duplicate within distance k → sliding window Set
  2. III — nearby in value and index → buckets / tree map
function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const window = new Set<number>();
  for (let i = 0; i < nums.length; i++) {
    if (window.has(nums[i])) return true;
    window.add(nums[i]);
    if (window.size > k) window.delete(nums[i - k]);
  }
  return false;
}

Interview delivery

  1. Restate.
  2. Brute → sort → set.
  3. Prefer early-exit Set.
  4. O(n)/O(n).
  5. Mention nearby-duplicate follow-up.

Mental model

Membership query: “have I seen this value?” Hash set is the default tool. Sorting is the comparison-model alternative when hash tables are disallowed or memory is tighter for some reason.

Production cousin: detecting duplicate request ids, double-submit tokens, or React keys collisions in a list.

Complexity tradeoffs to say

Approach Time Space Mutates input?
Nested loops O(n²) O(1) no
Sort in place O(n log n) O(1) yes
Sort copy O(n log n) O(n) no
Set early exit O(n) avg O(n) no
Set size compare O(n) O(n) no

Out-loud answer

“Return true if any value repeats. I’ll scan into a Set and return on first collision — O(n) time O(n) space. Sort is O(n log n) if hashing is off the table. Follow-up: duplicates within distance k uses a sliding window set.”

Further reading