Arrays & Hashing crash course ↗ · 03

217. Contains Duplicate

Decide whether any value appears more than once. The naive approach compares all pairs in O(n²); the clean answer streams through once, remembering everything it has seen in a hash set and stopping the instant it meets a repeat.

● EasyHash SetSeen-so-farTypeScript

PROBLEM What we're solving

Return true if any value in nums appears at least twice, else false. For [1,2,3,1] → true (the 1 repeats). For [1,2,3,4] → false.

KEY IDEA A set is a membership oracle

Insight → a hash Setanswers "have I seen this exact value before?" in O(1). Stream through the array; the first time a value is alreadyin the set, you've found a duplicate and can return immediately.

You don't need counts or positions — only the binary fact of membership. That's exactly what a set gives you, more cheaply than a map.

RECIPE One pass, early exit

  • 1 · For each value, ask the set: is it already here?
  • 2 · If yes → duplicate found, return true right away.
  • 3 · If no → add it to the set and continue.
  • 4 · Survived the whole array → no duplicates, return false.
Classic confusion → the early return matters. On a duplicate-heavy array you stop at the first repeat, not after the full scan — worst case is still O(n), but average case exits fast. A neat one-liner — new Set(nums).size !== nums.length — is correct but always builds the whole set (no early exit).

COST Complexity & alternatives

Sort then scan
O(n log n)
Duplicates become adjacent. O(1) extra space.
Hash set
O(n)
O(n) time, O(n) space. Early exit.

Space vs time

Sorting trades the set's O(n) space for O(1) (in place) but costs O(n log n) time. If memory is tight, sort; if speed matters and memory is fine, the set wins. State this tradeoff out loud — interviewers love it.

Pattern transfer → the same "seen set" idea underlies Valid Anagram (counts), Longest Consecutive Sequence, Happy Number (cycle via seen set), and dedup steps inside 3Sum.

RUN IT Watch the set grow until a repeat

step 0 / 7
STARTEmpty set. Scan each value: if it's already in the set, it's a duplicate.
1function containsDuplicate(nums: number[]): boolean {
2▶  const seen = new Set<number>();
3  for (const x of nums) {
4    if (seen.has(x)) return true;  // repeat → done
5    seen.add(x);
6  }
7  return false;                    // all unique
8}
1
0
2
1
3
2
1
3
Seen set
empty
Status
—
current iin the setduplicate
slowfast

TYPESCRIPT The solution, annotated

containsDuplicate.ts
function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;  // repeat → done
    seen.add(x);
  }
  return false;                    // all unique
}

Reading it block by block

Line 2 — the set. A Set stores only membership — no counts, no indices — which is all this problem needs.
Line 4 — check first.If the value is already present, we've seen it before; return true immediately. This early exit is the difference from the always-build-the-whole-set one-liner.
Line 5 — then add. Record the value so future iterations can detect it as a repeat.
Line 7 — survived. Falling out of the loop means every value was unique.
Complexity → O(n) time (each element visited once, O(1) set ops), O(n) space worst case (all unique). The sort-based alternative is O(n log n) time, O(1) space.

INTERVIEWFollow-ups they'll ask

  • "Do it with O(1) extra space." Sort in place, then check adjacent equal elements → O(n log n) time.
  • "Contains Duplicate II — within distance k?" Slide a window of size k as a set; add/remove as you go.
  • "Contains Duplicate III — values within t and indices within k?" Bucketing or a balanced BST / ordered set.
  • "Edge cases?" Empty array and single element both return false; the loop handles them naturally.

OPTIMAL Hash Set

containsDuplicate.ts
function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;  // repeat → done
    seen.add(x);
  }
  return false;                    // all unique
}
Complexity → O(n) time (each element visited once, O(1) set ops), O(n) space worst case (all unique). The sort-based alternative is O(n log n) time, O(1) space.

ALT 1 Brute force — compare every pair

O(n²) time · O(1) space

The most literal reading: for each element, scan every later element and return true the moment two are equal. No extra data structures.

approach-2.ts
function containsDuplicate(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;
}
Note → The nested scan is O(n²) and degrades badly on large arrays. Trading O(n) memory for a Set (the optimal) lets each lookup be O(1), finishing in a single O(n) pass.

MNEMONIC The one-liner

"Seen it? Done. Haven't? Add it and move on."

TRIGGERS When you see ___ → reach for ___

"any element repeated?"hash Set, early exit
only membership matters (not count)Set over Map
"within distance k"sliding-window Set
O(1) space requiredsort + adjacent check

SKELETON The reusable shape

skeleton.ts
const seen = new Set<number>();
for (const x of nums) {
  if (seen.has(x)) return true;
  seen.add(x);
}
return false;

FLASHCARDS Tap to flip

Set vs Map for this problem — which and why?
A Set. We only need membership ("seen it?"), not counts or indices.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 8
QUESTION 01
Optimal time complexity using a hash set?
QUESTION 02
Why prefer a Set over a Map here?
QUESTION 03
What's the O(1)-extra-space approach?
QUESTION 04
For [1,2,3,4] the function returns:
QUESTION 05
On [2,2,...] (repeat at the front), the set approach:
QUESTION 06
Empty array [] returns:
QUESTION 07
#217 · Contains DuplicateDecide whether any value appears more than once by streaming through the array once and remembering everything seen in a hash set, stopping the instant a repeat appears.Which algorithmic approach does this primarily use?
QUESTION 08
#217 · Contains DuplicateDecide whether any value appears more than once by streaming through the array once and remembering everything seen in a hash set, stopping the instant a repeat appears.Which implementation correctly solves it?