HashSet for Duplicate / Existence Check

The problem with scanning

You have a list of 10 000 numbers and want to know if any two are the same. The obvious approach: for each number, scan the rest of the list to see if it appears again. That is O(n²) comparisons.

There is a faster way. You don't need to find which pair is a duplicate — only whether one exists. For that, you need a structure that answers "have I seen this?" in constant time.

The bouncer with a stamp

The one idea to remember

The skeleton

seen = set()
for x in arr:
    if x in seen:        # O(1) lookup
        # x is a duplicate — act on it
    seen.add(x)          # O(1) insert

That's the entire pattern. Everything else is a variation on where to add, where to query, and what "act on it" means.

Variant 1 — Contains Duplicate (LC #217)

Does the array contain any duplicate?

def containsDuplicate(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True      # duplicate found → short-circuit
        seen.add(num)
    return False

Variant 2 — Contains Duplicate within k distance (LC #219)

Does any duplicate exist where the two copies are at most k index positions apart?

def containsDuplicateII(nums: list[int], k: int) -> bool:
    window = set()
    for i, num in enumerate(nums):
        if num in window:
            return True
        window.add(num)
        if len(window) > k:
            window.remove(nums[i - k])   # slide: remove element k steps back
    return False

This is a sliding-window HashSet. The window always holds at most k elements. Checking membership against this bounded set answers "does a copy within k distance exist?"

Variant 3 — Longest Consecutive Sequence (LC #128)

This is the "aha" problem of the HashSet chapter.

Problem: given an unsorted array, find the length of the longest sequence of consecutive integers (e.g., [100, 4, 200, 1, 3, 2] → 4 because 1, 2, 3, 4).

Naive approach: sort, then scan. O(n log n).
HashSet approach: O(n). The trick is elegant.

The key insight: only start counting from sequence heads

A number x is a sequence head if x - 1 is not in the set. If x - 1 exists, then x is the middle of a sequence that was already (or will be) counted from the earlier head. Starting from the head prevents counting the same sequence multiple times.

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)    # O(n) build
    best = 0

    for x in num_set:
        if x - 1 not in num_set:     # x is a sequence head
            length = 1
            while x + length in num_set:
                length += 1
            best = max(best, length)

    return best

Frame-by-frame for [100, 4, 200, 1, 3, 2]

num_set = {1, 2, 3, 4, 100, 200}

x = 100 → is 99 in set? No → head. Count: 100, 101? No → length = 1.
x = 4   → is 3 in set? Yes → not a head. Skip.
x = 200 → is 199 in set? No → head. Count: 200, 201? No → length = 1.
x = 1   → is 0 in set? No → head. Count: 1, 2 ✓, 3 ✓, 4 ✓, 5? No → length = 4.
x = 3   → is 2 in set? Yes → not a head. Skip.
x = 2   → is 1 in set? Yes → not a head. Skip.

best = 4  ✅

Why is this O(n) and not O(n²)?

The while loop extends from a head and visits each element of the sequence once. Across all heads, the total number of while iterations equals the total number of elements — O(n). The outer for loop is also O(n). Combined: O(n).

Set vs. dict — when to use which

A common beginner mistake: using a dict with dummy values ({x: True}) when a set is all you need. Use the simplest structure.

Cycle detection via HashSet (Floyd alternative)

If you want to detect a cycle in a linked list or sequence of jumps, HashSet gives you a simple O(n) space alternative to Floyd's two-pointer algorithm:

def hasCycle(head):
    seen = set()
    node = head
    while node:
        if id(node) in seen:
            return True
        seen.add(id(node))
        node = node.next
    return False

Floyd's algorithm is O(1) space and generally preferred in interviews, but the HashSet version is O(1) time per step and easier to adapt for "which node is the cycle entry?"

Where to spot this pattern

Trigger words:

• "contains duplicate"
• "any repeated element"
• "check existence" or "has this appeared before"
• "longest consecutive" or "consecutive integers"
• "visited" tracking during graph/path traversal
• "intersection" or "union" of two arrays (use set operations)

5 disguises:

1. Contains Duplicate (LC #217): direct bouncer pattern.
2. Contains Duplicate II (LC #219): sliding window of size k.
3. Longest Consecutive Sequence (LC #128): head-only counting.
4. Happy Number (LC #202): cycle detection — has a number appeared in the digit-sum sequence?
5. Intersection of Two Arrays (LC #349): convert both to sets, set1 & set2.

Common traps

Complexity

Say it like a pro (interview one-liner)

"I'll use a HashSet to answer 'have I seen this?' in O(1) time per element, giving O(n) total for a single pass. For Longest Consecutive, I extend only from sequence heads — elements where x - 1 is absent — so each element is visited by the inner loop at most once, keeping the total to O(n)."

seen = set()
for x in arr:
    if x in seen:   # O(1) — have I seen this?
        # duplicate / cycle / hit
    seen.add(x)     # O(1) — stamp it

num_set = set(nums)
for x in num_set:
    if x - 1 not in num_set:      # sequence head only
        count from x upward with while x+length in num_set

Check yourself

Practice problems

Next up: Custom Hash Design — when you need to hash composite keys (pairs, tuples, strings with structure), and how to design a hash function that avoids collisions.