Hash Sets & Their Patterns

Membership testing in O(1), eliminating duplicates and tracking visited nodes

Think of the guest list at a party. Each name is on it once. If someone already on the list tries to sign again, nothing changes, they are already in. And the person at the door can check "are you on the list?" in a blink, however long the list gets.
A set is exactly that: a bag of items where each one appears only once, and you can ask "is this already in here?" and get an answer instantly. Build one below.

That gives a set two everyday superpowers:

Throw away duplicates. Drop a whole pile of things in and you are left with one of each, for free.

Remember what you have seen. Tick things off as you go, and asking "did I see this already?" is instant. This is why graph searches keep a visited set, so they never walk into the same place twice.

Three plain moves: add something, ask is it in here?, or remove it. All three are instant, O(1), and here is the neat part: a set is really just the locker wall from the last lesson (a hash map) that keeps only the names and throws away the values. Same magic, one job.

Longest consecutive sequence, O(n)python

def longest_consecutive(nums):
    num_set = set(nums)  # O(1) lookups
    longest = 0

    for n in num_set:
        # Only start counting from the beginning of a sequence
        if n - 1 not in num_set:
            current = n
            streak = 1
            while current + 1 in num_set:
                current += 1
                streak += 1
            longest = max(longest, streak)

    return longest

print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # → 4 (1,2,3,4)

🤔Quick Check

You're doing BFS on a graph. Why use a "visited" set instead of a list?

🎯

Phase Complete!

Hash Maps & Sets

Hash maps and sets are some of the most powerful tools in your arsenal. You'll use them in almost every medium/hard interview problem. Now for trees!

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1easy

⏱ 00:00

Happy Number

A happy number: repeatedly sum the squares of its digits. If you reach 1, it's happy. If you enter a cycle, it's not.
Expected output: True

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next