Yash Gandhi

Posted on May 17

Hash Set Pattern — LeetCode #217: Contains Duplicate

#leetcode #dsa #typescript #python

Prerequisites: Loop Invariants (to understand why this works, not just how) | Running Sum (#1480) (the accumulator pattern this builds on). If you haven't read them, the solution will still make sense; the invariant section will click deeper if you have.

The Problem (15 seconds)

Given an integer array, return true if any value appears at least twice.

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

Input:  [1, 2, 3, 4]
Output: false        // all distinct

LeetCode #217 — Contains Duplicate

My First Instinct

I read "does any value appear twice?" and thought: for each number, check if it appears again later. That's a nested loop:

// Brute force — for each element, scan the rest
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;
}

O(n²). On paper this is what your hand would do — pick a number, scan the rest. (You'll see this exact same instinct in Two Sum (#1) later — it's the natural human approach, and it's always the starting point.)

The Reframe

I'm checking: "does this number exist somewhere else in the array?"

Flip it: "have I already seen this number?"

If I keep a set of numbers I've visited so far, the answer is one lookup away. That's a hash set — O(1) to check, O(1) to add.

The Invariant

At step i, seen contains every element from indices 0 to i-1.

If nums[i] is already in seen, we've found a duplicate. If we finish the loop without finding one, all values are unique.

This is the exact same invariant you'll use in Two Sum (#1) — just simpler. There, you store value→index pairs. Here, you only need the values.

Solution

TypeScript:

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

Python:

def contains_duplicate(nums: list[int]) -> bool:
    seen: set[int] = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

Complexity: O(n) time, O(n) space.

Dry Run

nums = [1, 2, 3, 1]

num=1: seen={}        → 1 not in seen → seen={1}
num=2: seen={1}       → 2 not in seen → seen={1,2}
num=3: seen={1,2}     → 3 not in seen → seen={1,2,3}
num=1: seen={1,2,3}   → 1 IS in seen! → return true ✓

The One-Liner Temptation

You might think: "Just check if Set(nums).size !== nums.length."

const containsDuplicate = (nums: number[]): boolean =>
  new Set(nums).size !== nums.length;

This works and is clean. But it always processes the entire array — even if the duplicate is at index 1. The loop version exits early. For interviews, show the loop version first (it demonstrates you understand the pattern), then mention the one-liner as an alternative.

Where This Pattern Shows Up Again

Problem	What changes
Two Sum (#1)	Instead of just checking existence, you also store the index
Valid Anagram (#242)	Instead of a Set, you use a Map to count frequencies
Group Anagrams (#49)	Hash map with a computed key (sorted string)
Longest Substring Without Repeating Characters (#3)	Set + sliding window

The "have I seen this?" question is everywhere. This problem is where you practice it in its purest form.

What I Learned

"Have I seen this before?" = hash set. The simplest version of the lookup pattern. No values to store, just existence. This is the question behind dozens of problems — learn to hear it, even when the problem doesn't phrase it this way.
The universal tradeoff: spend space to save time. The brute force checks all pairs (O(n²) time, O(1) space). The hash set remembers what it's seen (O(n) time, O(n) space). Almost every O(n²) → O(n) optimization works the same way: store previous results so you don't re-scan. This is the same tradeoff in Two Sum, Valid Anagram, and Subarray Sum Equals K.
The invariant is the same one Two Sum uses. seen contains everything visited so far. If you understand it here, Two Sum's invariant is just one step further (storing indices alongside values). Valid Anagram (#242) goes further still — storing counts instead of just existence.
TypeScript vs Python: Set.has() vs in set — Python reads more naturally, but TypeScript's generic Set<number> gives you type safety. Both are O(1) average.

What's a problem where you used a nested loop, solved it, and only later realized a hash set would've done it in one pass?

Next in the series: Valid Anagram (#242) — where you'll take the hash set one step further and store counts instead of just existence. Then we bring all three patterns together in Two Sum (#1).

DEV Community