3. Hashing

Key Insight

A hash map trades $O(n)$ space for $O(1)$ average lookups. The canonical use is counting frequency or mapping a value to its index/position — converting $O(n^2)$ brute force to $O(n)$.

Python's Hash Containers

from collections import defaultdict, Counter

# defaultdict — auto-initialises missing keys
freq: dict[str, int] = defaultdict(int)
graph: dict[int, list] = defaultdict(list)
memo: dict = defaultdict(lambda: float("inf"))

# Counter — frequency map with extras
c = Counter("abracadabra")    # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
c.most_common(2)               # [('a', 5), ('b', 2)]
c1 + c2                        # union (add counts)
c1 - c2                        # subtract (drop zero/negative)
c1 & c2                        # intersection (min counts)
c1 | c2                        # union (max counts)

---

3.1 Frequency Map Patterns

# --- Two Sum (unsorted, return indices) ---
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        comp = target - x
        if comp in seen:
            return [seen[comp], i]
        seen[x] = i
    return []

# --- Group Anagrams ---
def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[tuple, list] = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

# --- Top K Frequent Elements — O(n log k) ---
import heapq
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    return heapq.nlargest(k, freq, key=freq.get)

# --- Top K Frequent — O(n) bucket sort ---
def top_k_frequent_linear(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    buckets: list[list] = [[] for _ in range(len(nums) + 1)]
    for num, cnt in freq.items():
        buckets[cnt].append(num)
    res = []
    for i in range(len(buckets) - 1, 0, -1):
        res.extend(buckets[i])
        if len(res) >= k:
            return res[:k]
    return res

---

3.2 Rolling Hash (Rabin-Karp)

Use when: substring search, finding duplicate substrings in $O(n)$.

MOD = (1 << 61) - 1  # Mersenne prime
BASE = 131

def rolling_hash(s: str) -> list[int]:
    """Returns prefix hash array; hash of s[l:r+1] = query(h, p, l, r)."""
    n = len(s)
    h = [0] * (n + 1)
    p = [1] * (n + 1)
    for i, c in enumerate(s):
        h[i+1] = (h[i] * BASE + ord(c)) % MOD
        p[i+1] = p[i] * BASE % MOD
    return h, p

def query(h: list[int], p: list[int], l: int, r: int) -> int:
    """Hash of s[l..r] inclusive."""
    return (h[r+1] - h[l] * p[r-l+1]) % MOD

# Usage: find duplicate substring of length k
def has_duplicate_substring(s: str, k: int) -> bool:
    h, p = rolling_hash(s)
    seen = set()
    for i in range(len(s) - k + 1):
        hval = query(h, p, i, i + k - 1)
        if hval in seen:
            return True
        seen.add(hval)
    return False

---

3.3 Key CP Patterns

Problem type	Technique
Pair/count with complement	seen dict + target - x
Frequency / top-K	Counter + heapq.nlargest
Anagram grouping	sorted tuple as key
Substring deduplication	rolling hash
Sliding window distinct count	defaultdict(int) + delete when 0

---