Contains Duplicate — the hash set pattern

This is the first algorithms lesson. We’re starting the NeetCode 200 track, category by category. The first category is Arrays & Hashing, and the first problem is Contains Duplicate (LeetCode 217). But the lesson isn’t about the solution — it’s about the pattern you’ll reuse across dozens of problems.

The problem

Input:  [1, 2, 3, 1]
Output: true  (1 appears twice)

Input:  [1, 2, 3, 4]
Output: false (all unique)

Simple to state. The question is: how fast can you check?

Approach 1: Brute force — compare every pair

The obvious approach: for each element, scan the rest of the array and check for a match.

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

This works. But the nested loop means: for an array of n elements, you do up to n(n-1)/2 comparisons — roughly n²/2. That’s O(n²) time. For 10,000 elements, that’s up to 50 million comparisons.

Approach 2: Hash set — check as you build

Instead of comparing every pair, ask a simpler question as you walk through the array: “have I seen this value before?” If you can answer that in O(1) time, you only need one pass.

A hash set does exactly that. You store each value as you see it. Before adding a new value, check if it’s already in the set. Hash set lookup is O(1) on average — constant time, regardless of how many elements are in the set.

function containsDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;  // O(1) check
    seen.add(n);                    // O(1) insert
  }
  return false;
}

One pass through the array, with O(1) work per element. That’s O(n) time. The tradeoff: you store up to n elements in the set, so it’s O(n) space.

The real benchmark

I ran both approaches on arrays of increasing size (30 iterations each, median reported, worst case = no duplicate). Here’s what happened:

Look at the red line (brute force) vs the green line (hash set). As n grows, the gap widens quadratically:

• n = 1,000: hash set is 2.5× faster
• n = 5,000: hash set is 19× faster
• n = 10,000: hash set is 50× faster

The speedup isn’t constant — it grows with n. That’s the visual signature of O(n²) vs O(n).

The pattern: “have I seen this before?”

When you need to check if something exists or has been seen, use a hash set for O(1) lookup. Trade O(n) space for O(n) time instead of O(n²).

The same pattern appears in: Two Sum (seen this complement before?), Group Anagrams (seen this signature before?), and many more. Once you internalize “hash set = instant membership check,” these problems all become one-pass.

The transfer question

From Day 1 → Day 4: How is a hash set like a database index? What do they trade, and what do they gain?

Answer (click to reveal)

Both solve the same fundamental problem: “how do I find something fast?” A database index (Day 1) is a sorted structure (B-tree) that makes read lookups O(log n) instead of O(n) — it trades write speed + storage for read speed. A hash set (Day 4) is a hash-based structure that makes membership checks O(1) instead of O(n) — it trades O(n) space for O(1) lookup. The index is optimized for a database (persistent, sorted, range queries). The hash set is optimized for in-memory algorithms (ephemeral, unsorted, point lookups). But the core idea is identical: trade space to buy time on reads.

The tradeoff (name it in interviews)

• O(n) space — you store up to n elements in the set. For most problems this is acceptable. For extremely memory-constrained environments, the O(1)-space sort-then-scan approach (O(n log n) time) might be preferable.
• Hash collisions — worst case, hash set lookup degrades to O(n) if every key hashes to the same bucket. In practice, with a good hash function, this almost never happens. But it’s why we say “O(1) average.”

Check your understanding