Hash set / map

How does Hash set / map work?

A hash function turns a key into a slot number. The value is written at that slot.

A lookup runs the same function again. It lands on the slot directly, without scanning anything.

Two keys can hash to the same slot. The structure keeps both and compares the keys themselves.

A set stores keys and nothing else. Use it for the question have I seen this.

A map stores a value beside each key. Use it for counts, indices or the last position seen.

Insert, lookup and delete each cost O(1) on average. The price is O(n) memory for the keys.

1. seen = {}Looking for the first repeated value in [3, 1, 3, 4].
2. seen = {3}3 has not been seen before. It goes into the set.
3. seen = {3, 1}1 is new as well. The set now holds two keys.
4. seen = {3, 1}3 comes round again. The set already holds it.
5. answer = 3The answer returns at once. The last element is never read.

function firstDuplicate(arr) {
    const seen = new Set();
    for (const x of arr) {
        if (seen.has(x)) return x;
        seen.add(x);
    }
    return null;
}

A worked example of Hash set / map

Two sum on unsorted data

You get an unsorted array and a target number. Return the indices of two values that add up to it.

Sorting would destroy the original indices. So the array has to stay as it is.

Walk the array once. For each value, work out the complement the target still needs.

If the map already holds that complement, the pair is found. Otherwise store the value with its index.

function twoSum(nums, target) {
    const seen = new Map(); // value -> index

    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];

        if (seen.has(need)) {
            return [seen.get(need), i];
        }

        // stored after the lookup, so a value never pairs with itself
        seen.set(nums[i], i);
    }

    return [];
}

When should you use Hash set / map?

These phrases in a problem statement point here:

• •have I seen this before
• •count how many of each
• •find duplicates
• •does a matching/complement value exist
• •data is in any order / unsorted

What is Hash set / map confused with?

• Two pointers (opposite ends): Two pointers need a sorted array and use no extra memory. Hashing is the answer when sorting is off the table.
• Sliding window (variable): A window answers a question about one contiguous span. A plain map has no idea of a span.
• Non-comparison sort (counting / radix): Counting sort also tallies frequencies, but it needs small integer keys. A map takes any key at all.
• Trie (prefix tree): A trie shares prefixes between keys, so it can answer prefix queries. A map only matches whole keys.
• Prefix sums: Prefix sums answer range questions over values kept in order. A hash keeps no order.

Common mistakes with Hash set / map

• Storing before the lookup

  Insert the value only after checking. Otherwise a value can pair with itself.

• Using a plain object for keys

  An object silently turns every key into a string, so 1 and "1" collide. Use Map instead.

• Counting without a default

  Reading a missing key gives undefined, and undefined plus one is NaN. Start each count at zero.

• Paying for memory you did not need

  If the data is already sorted, two pointers cost nothing extra. Hash only when the order is useless.

Which interview problems use Hash set / map?

• Two sum: Store each value with its index and look up the complement.
• Contains duplicate: A set that rejects a repeat answers this in one pass.
• Valid anagram: Count the letters of one word, then subtract the other.
• Group anagrams: The sorted word is the key. The group is the value.
• Top k frequent elements: Count with a map, then take the k largest counts.
• Longest consecutive sequence: A set lets you ask whether x minus one exists.
• Subarray sum equals k: Store how often each running total has appeared.

What is the time and space complexity of Hash set / map?

O(n)

n up to 1e6 unsorted values gives O(n) time. Space is O(n), because every distinct key is stored.