Topic: Learning notes

LeetCode 217: Contains Duplicate in TypeScript with a Set

Compare a Set's size with the array length, or stop early during one scan, while explaining the Set solution's correctness and expected O(n) complexity.

This problem is not about sorting. It asks whether a value has appeared before. A Set keeps unique values, which matches that question directly.

Problem

Original problem: LeetCode 217: Contains Duplicate

Given an integer array nums, return true when any value appears at least twice. Return false when every value is distinct.

Compare the Set size directly

function containsDuplicate(nums: number[]): boolean {
  return new Set(nums).size !== nums.length;
}

This version is correct. A Set keeps only unique values, so a size smaller than the original array length proves that at least one value was repeated.

It still visits every element and builds the complete Set. Its time is therefore expected O(n), and its auxiliary space is O(n), not O(1). Constructing the Set processes the input and can retain n distinct values.

Scan once and stop on the first duplicate

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

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

    seen.add(num);
  }

  return false;
}

The asymptotic complexity is the same. This form can return as soon as it finds a duplicate near the beginning, and it makes each step easier to explain in an interview.

Why the scan is correct

Before processing each num, seen contains exactly the distinct values from the earlier positions.

When seen.has(num) is true, num has appeared at an earlier index. The array therefore contains a duplicate, so returning true is correct. When it is false, adding num preserves the condition for the next iteration.

If the loop ends without a match, every value was added only on its first occurrence. No value appears twice, so returning false is correct.

Complexity

Both Set versions have expected O(n) time and O(n) auxiliary space in the worst case. In the hash-set model commonly used in interviews, each has() and add() operation is expected O(1). The JavaScript specification requires average access to be sublinear, rather than requiring one fixed internal implementation. MDN’s Set reference describes that requirement.

Minimal verification

import assert from "node:assert/strict";

assert.equal(containsDuplicate([1, 2, 3]), false);
assert.equal(containsDuplicate([-1, -3, 1]), false);
assert.equal(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]), true);
assert.equal(containsDuplicate([2]), false);

Common mistakes

• Calling new Set(nums) an O(1) operation. It reads the input and can retain every distinct number.
• Sorting to avoid extra space. That works, but takes O(n log n) time and mutates the input if sorted in place.
• Continuing after a duplicate is found. A boolean-returning solution can stop immediately.
• Listing expected results without executable assertions. Assertions check the output.

Transferable idea

When the question is only whether a value has appeared, start with a Set. Use a Map when the solution also needs an index, a count, or another value. Separating membership from extra data avoids choosing a heavier structure than the problem needs.

References

• LeetCode 217: Contains Duplicate: original problem, examples, and constraints.
• MDN: Set: unique-value semantics, has(), add(), and average access requirements.
• ECMAScript: Set Objects: the JavaScript specification for Set.
• Node.js: assert.equal(): basic equality assertions.