Hash maps and sets

Problem

Brute force on arrays is mostly a story of re-scanning: for each element, look through the rest of the input for a partner, a duplicate or a match. That costs O(n²). A hash table turns the inner scan into a single lookup, so you trade O(n) extra memory for a drop from O(n²) to O(n). Whenever you catch yourself writing "for each x, find a y such that…", ask whether y can be computed from x and looked up instead.

Intuition

Think of a coat check. You hand over a coat and get a numbered ticket; later the ticket takes you straight to the right hook instead of a search along the whole rack. A hash table makes the ticket from the key itself: a hash function turns the key into a number, and that number picks a bucket. Looking a key up repeats the same calculation and goes straight to the same bucket.

The pattern comes from reading a problem backwards. "Find a pair that sums to 9" sounds like a search over pairs. But standing on one number, say 7, the partner you need is already determined: it is 2. So the problem is not "search for a pair" but "for each number, has its one possible partner already gone by?" Remembering what has gone by is exactly what a hash table is for.

The map is a memory of the past; each step asks it one question.

Mechanics

How a hash table works

A hash table keeps an array of buckets. To store a key, compute hash(key) mod size and put the key in that bucket. To look it up, compute the same index and look only in that bucket. Two different keys can land in the same bucket (a collision); the simplest fix, separate chaining, keeps a short list in each bucket and scans it. Python's built-in dict and set use open addressing instead (probing for another free slot in the same array) but the consequences are the same.

Collisions lengthen one chain; resizing the table keeps chains short.

The invariants

Hash tables stay fast because of two promises. First, equal keys always hash equally, so a key can only ever be in one bucket. Second, the table is kept from getting too full: when the load factor (keys divided by buckets) passes a limit, the table doubles and every key is re-hashed. With a good hash function the expected chain length stays near the load factor, so lookup, insert and delete are O(1) on average, and doubling makes insert O(1) amortized.

For the solving patterns the invariant is about the map's contents, not its internals: before processing element i, the structure answers correctly for elements 0 to i − 1. Complement maps are correct because every valid pair (a, b) with a before b is found when b is processed, since a is already stored. Look up first, then insert, so an element never pairs with itself.

What can be a key

A key must be hashable: immutable, with a stable hash. Ints, strings, bytes and tuples of those work; lists, sets and dicts do not. To use a list or a grid state as a key, convert it: tuple(row), "".join(chars), or frozenset(items). Floats work but suffer from rounding, so avoid them as keys.

Worked example

Two Sum on [11, 3, 15, 8, 2, 7] with target 9. At each step the table shows the complement we need, whether it is already in the map, and the map as it stood when the number was examined (before inserting it).

The pass stops at i = 5 and returns indices 4 and 5, after 6 lookups. A nested loop would have compared up to 15 pairs on this input.

A second shape, the set used to avoid sorting. Longest Consecutive Sequence on [100, 4, 200, 1, 3, 2, 101, 5, 102]: only start counting at a number whose predecessor is missing, then walk upward.

The longest run has length 5. Making this work took 18 set lookups for 9 distinct numbers, at most 2n: every number is stepped over once as a member of a run and checked once as a possible start. Without the "no predecessor" test, a long run would be re-walked from every number inside it and the cost would be quadratic.

Implementation

def has_duplicate(nums):                       # seen-set
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False


def two_sum(nums, target):                     # complement map: value -> index
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:                 # look up before inserting
            return [seen[target - x], i]
        seen[x] = i
    return []


from collections import defaultdict

def group_by_key(items, key):                  # canonical key -> group
    groups = defaultdict(list)
    for item in items:
        groups[key(item)].append(item)
    return list(groups.values())


def longest_consecutive(nums):                 # set instead of sorting
    members, best = set(nums), 0
    for x in members:
        if x - 1 not in members:               # x starts a run
            length = 1
            while x + length in members:
                length += 1
            best = max(best, length)
    return best


class MyHashSet:                               # separate chaining, fixed bucket count
    def __init__(self, size=1009):
        self.buckets = [[] for _ in range(size)]

    def _chain(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def add(self, key):
        chain = self._chain(key)
        if key not in chain:
            chain.append(key)

    def remove(self, key):
        chain = self._chain(key)
        if key in chain:
            chain.remove(key)

    def contains(self, key):
        return key in self._chain(key)

Variations and edge cases

• Map instead of set. MyHashMap stores (key, value) pairs in the chain and, on a repeated key, replaces the existing pair rather than appending a second one.
• Random access with deletion. To pick a random element in O(1), keep the values in a list plus a dict from value to list index. Delete by overwriting the slot with the last element, updating that element's index, and popping the tail.
• One set per rule. For Sudoku, keep a set for each row, each column and each 3 × 3 box (index (r // 3, c // 3)) and reject a digit that is already in any of them.
• Rank maps. For custom orderings such as an alien alphabet, map each symbol to its position and compare words by those ranks.
• Edge cases: inserting before looking up (an element pairs with itself), duplicate values in complement problems (target 6 with [3, 3] works only if you look up first), hashing a mutable list, relying on dict order for answers, and a prefix such as "abc" being a prefix of another key in custom tables.

Complexity and tradeoffs

• Time is O(n) for one pass with O(1) average operations. The worst case for a single operation is O(n) if every key collides, which a sane hash function makes vanishingly unlikely; say "O(1) average" rather than "O(1)".
• Space is O(n) for the table, the price of avoiding rescans.
• Baselines. Brute force is O(n²) time and O(1) space. Sorting first is O(n log n) time and often O(1) extra space, and can be the better answer when memory is tight or when two pointers apply afterwards.
• When it fails. A hash table has no order: it cannot give you the next larger key or the minimum cheaply. For ordered queries use sorting with binary search, a heap, or a balanced tree. Hashing also adds a constant factor; for tiny alphabets an array of counts is faster than a dict.
• Hash flooding. Adversarial input can force collisions. Python randomizes string hashes per process for this reason; it is not a concern in interviews.

Problems

The home problems use all three shapes: seen-sets (duplicates, Sudoku), complement and rank maps (Two Sum, the alien dictionary), set-based runs (Longest Consecutive Sequence) and the design questions that build the table itself. The "also uses" list shows how often a map shows up as a helper inside other patterns.

Easy

• 1. Two Sum Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Store each value's index as you go, so every new number only has to ask whether its complement has already been seen.
• 217. Contains Duplicate Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Add values to a set and stop at the first one already in it.
• 705. Design HashSet NeetCode 250
  Hash keys into a fixed number of buckets, each a small list, and resolve collisions inside the bucket.
• 706. Design HashMap NeetCode 250
  Use the same bucket array as a hash set but store key-value pairs and update a key's pair in place.
• 953. Verifying an Alien Dictionary NeetCode 250
  Map each letter to its rank and check that every adjacent pair of words is in order under that ranking.

Medium

• 36. Valid Sudoku Grind 169 NeetCode 150 NeetCode 250
  One pass records each digit in a set for its row, its column and its box, whose index is row//3 and col//3.
• 128. Longest Consecutive Sequence Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Put every number in a set and only start counting at numbers with no predecessor, so each run is walked once.
• 380. Insert Delete GetRandom O(1) Grind 169
  Keep values in an array for random picks and a map from value to index, and delete by swapping the value with the last element.
• 2013. Detect Squares NeetCode 150 NeetCode 250
  Count points, and for a query pick each stored point as the diagonal corner, then multiply the counts of the two other corners.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 13. Roman to Integer Easy
• 169. Majority Element Easy
• 202. Happy Number Easy
• 219. Contains Duplicate II Easy
• 3. Longest Substring Without Repeating Characters Medium
• 49. Group Anagrams Medium
• 105. Construct Binary Tree from Preorder and Inorder Traversal Medium
• 133. Clone Graph Medium
• 138. Copy List with Random Pointer Medium
• 146. LRU Cache Medium
• 437. Path Sum III Medium
• 525. Contiguous Array Medium
• 560. Subarray Sum Equals K Medium
• 721. Accounts Merge Medium
• 752. Open the Lock Medium
• 763. Partition Labels Medium
• 846. Hand of Straights Medium
• 981. Time Based Key-Value Store Medium
• 37. Sudoku Solver Hard
• 127. Word Ladder Hard
• 336. Palindrome Pairs Hard
• 460. LFU Cache Hard
• 588. Design In-Memory File System Hard
• 815. Bus Routes Hard
• 895. Maximum Frequency Stack Hard

Connections

Counting and bucketing replaces the stored index with a count. Prefix sums with a map extend the complement idea to running totals: two equal totals mean the stretch between them sums to zero. Sliding windows keep a map of what is inside the window, and graph searches keep a set of visited nodes.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: chapter 11 (hash tables: chaining, open addressing, universal hashing).
• Sedgewick and Wayne, Algorithms: section 3.4 (hash tables).
• Steven Skiena, The Algorithm Design Manual: the section on hashing and strings.
• Carter and Wegman, "Universal classes of hash functions", Journal of Computer and System Sciences 18 (1979).
• Python documentation: the dict and set types and collections.defaultdict.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.