Hash Set | Engineering Interview Kit

Concept

A Hash Set is a simplified version of a Hash Map.
While a Hash Map stores Key-Value pairs, a Hash Set strictly stores Keys only.

It is used specifically for one mathematical purpose: Ensuring uniqueness and providing instant $O(1)$ lookups.

If you have an array of 100,000 numbers, and you want to know if the number 42 is in it, array.includes(42) takes $O(N)$ time. If you convert the array into a Set, set.has(42) takes instant $O(1)$ time.

Implementation in JavaScript

// Initializing from an Array (Automatically removes all duplicates!)
const uniqueNumbers = new Set([1, 2, 2, 3, 3, 3, 4]);
console.log(uniqueNumbers); // Set { 1, 2, 3, 4 }

// O(1) Insertion
uniqueNumbers.add(5);
// Adding a duplicate does absolutely nothing (fails silently)
uniqueNumbers.add(5); 

// O(1) Lookup
if (uniqueNumbers.has(3)) {
    console.log("Found 3 instantly!");
}

// O(1) Deletion
uniqueNumbers.delete(1);

// Convert back to Array
const finalArray = Array.from(uniqueNumbers);

The “Visited” Pattern

The absolute most common use case for a Hash Set in interviews is tracking Visited Nodes to prevent infinite loops.

If you are exploring a Graph, or traversing a Linked List with a cycle, you can easily get trapped exploring the same nodes over and over forever.

By passing a Set along with your recursive function:

When you arrive at a node, you immediately check if (visited.has(node)) return;.
If you haven’t been there, you add it: visited.add(node).
You explore its neighbors.

This simple $O(1)$ check guarantees you never process the same data twice.

Longest Consecutive Sequence

Problem: Given an unsorted array of integers, return the length of the longest consecutive elements sequence. You must write an $O(N)$ algorithm. (LeetCode 128).
Input: [100, 4, 200, 1, 3, 2] -> Output: 4 (The sequence is 1, 2, 3, 4).

If we sort the array, it takes $O(N \log N)$ . The prompt explicitly demands $O(N)$ . We must use a Hash Set.

The Strategy:

Throw all numbers into a Set ( $O(N)$ time).
Loop through the Set.
The Trick: We only want to start counting a sequence if the number is the absolute bottom start of a sequence. How do we know if 3 is the start? We check if 2 exists! If 2 exists, 3 is not the start. We skip 3 entirely.
When we find a true start (e.g., 1, because 0 is not in the set), we start a while loop counting upwards (set.has(2), set.has(3)…).

function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);
    let longestStreak = 0;

    for (let num of numSet) {
        // Is this number the true start of a sequence?
        // (If the number right below it exists, this is NOT the start).
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            // Count upwards!
            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

Interview Questions

Q: In the longestConsecutive solution, there is a while loop nested inside a for loop. Shouldn’t that be $O(N^2)$ time?
A: No, it is strictly $O(N)$ time. Because of the if (!numSet.has(num - 1)) check, the inner while loop only executes if the number is the absolute bottom start of a sequence. Therefore, every single number in the entire set is visited by the inner while loop an absolute maximum of exactly one time. $N$ outer iterations + $N$ inner iterations = $2N$ , which simplifies mathematically to $O(N)$ .

Q: A developer needs to deduplicate an array of objects: [{id: 1}, {id: 1}, {id: 2}]. They write const unique = Array.from(new Set(array)). Does this work?
A: No. Just like Map, a JavaScript Set evaluates uniqueness based on the exact memory reference of an Object, not its internal values. Because the two {id: 1} objects were instantiated separately, they occupy different physical memory blocks. The Set views them as two completely unique items and will not filter them out. To deduplicate objects, the developer must manually iterate, using a Hash Map tracking the primitive id strings.